=Paper=
{{Paper
|id=None
|storemode=property
|title=Constructing Petri Net Transducers with PNTooL
|pdfUrl=https://ceur-ws.org/Vol-1160/paper23.pdf
|volume=Vol-1160
|dblpUrl=https://dblp.org/rec/conf/apn/Huber014
}}
==Constructing Petri Net Transducers with PNTooL==
https://ceur-ws.org/Vol-1160/paper23.pdf
Constructing Petri Net Transducers with PNTeooL
Markus Huber and Robert Lorenz
Department of Computer Science
University of Augsburg, Germany
firstname.lastname@informatik.uni-augsburg.de
Abstract This poster presents a tool for the modular construction of Petri net
transducers by means of several composition operations as for example union,
concatenation, closure, parallel and synchronous product and language composi-
tion. There are exports to PNML and several graphical output formats.
For the implementation, we use the SNAKES framework, which is a Python lib-
rary supporting the rapid prototyping of new Petri net formalisms and provides
many basic Petri net components and functionality.
In the context of our research activities, PNTeooL serves as a scientific prototype
for the development of an open library openPNT of efficient algorithms for the
construction, composition, simulation and optimisation of PNTs which can be
used in real world examples.
In [1] we introduced Petri net transducers (PNTs) and showed in [2] how they can
be successfully applied in the field of semantic dialogue modelling for translating utter-
ances into meanings. In [3] we presented a basic theoretical framework of PNTs.
In short PNTs are a formalism for the weighted translation of labelled partial orders
(LPOs), which are words consisting not of a total order between their symbols but of a
partial order. In this sense they are a generalisation of weighted finite state transducers
(FSTs) translating words.
e:y/0.25
t1
a:x/0.5 e:y/0.25
N1 N2 a:x/0.5
(a) A transducer N1 and a generator N2 . (b) Parallel product of N1 and N2 after tI has fired.
Figure 1. Some simple PNTs.
In Figure 1 one can see on the left side two simple PNTs called N1 and N2 . Like for
weighted FSTs input symbols, output symbols and weights are annotated to the transi-
tions. So the transition of N1 reads the symbol a and writes the symbol x (with weight
0.5) – thus N1 translates the word a into the word x (with weight 0.5). The symbol e
is used to denote empty input or output. So the PNT N2 is a generator which produces
the word y. The weights are elements of an algebraic structure called bisemiring [3]
which extends semirings by an additional operation. Thus, a bisemiring a set equipped
340 PNSE’14 – Petri Nets and Software Engineering
with three operations, namely addition, sequential multiplication and parallel multiplic-
ation, satisfying certain consistency properties (for example the existence of neutral
elements). Addition is used to combine the weights of alternative LPO-runs of a PNT,
sequential multiplication of weights is used for sequentially composed LPOs and the
weights of parallel composed LPOs are parallel multiplied. In the examples we use the
extended Viterbi semiring ([0, 1], max, ·, min).
As for FSTs there exist composition operations for combining simple transducers to
more complex ones. For example, Figure 1 shows on the right side the parallel product
of the PNTs – an operation which does not exist for FSTs. In figures, we omit an-
notations of the form e:e/1 where 1 is the neutral weight w.r.t. sequential and parallel
multiplication. The PNT realises the translation from the word a into the LPO w=xky
where k denotes the parallel composition of LPOs. There are more operators defined for
PNTs namely concatenation, union, closure, synchronous product and language com-
position of PNTs [3,2]. In Figure 2 on the right side the language composition of the
PNT N3 on the left side with the PNT shown on the right side of Figure 1 is illustrated.
Here, a transition from the first PNT is merged with a transition from the second PNT,
if the output of the first transition equals the input of the second one. The weight of the
merged transition labelled r,t3 is computed from the weights of the transitions labelled
r and t3 using sequential multiplication.
Note that PNTs are defined to always have a single source place which holds exactly
one token at the initial state. Furthermore a PNT has a single sink place and per defin-
ition only such LPO-runs are considered, which lead to a state where exactly the sink
place is marked by one token (the final state). Each LPO-run translates an LPO over
input symbols into an LPO over output symbols via a projection onto input symbols
resp. output symbols [3].
For such a formalism to be useful one needs a tool where PNTs can be implemented,
analysed, combined, simulated, drawn and the like. Since the PNT-formalism is new we
decided to start PNTeooL. We use the SNAKES framework [4] which is a Python library
supporting the rapid prototyping of new Petri net formalisms and provides many basic
Petri net components and functionality. Therefore we implemented PNTeooL as a Python
library extending SNAKES such that we essentially can use all the functionality already
provided by SNAKES. All graphics in this paper were generated by PNTeooL.
The support of graphical output serves as a possibility to check the implementation
and as a handy utility in the process of writing scientific papers. PNTeooL’s functionality
supports fast construction of concrete example PNTs for case studies. PNML export can
be used to analyse constructed example PNTs with other Petri net tools. In the context
of our research activities, PNTeooL serves as a scientific prototype for the development
of an open library openPNT of efficient algorithms for the construction, composition,
simulation and optimisation of PNTs which can be used in real world examples.
PNTeooL can be downloaded as a ZIP-archive from our website www.informatik.
uni-augsburg.de/EduCoSci/PNTooL. Assumed you have a working installa-
tion of Python, SNAKES, Graphviz, and dot2tex you only need to copy the py-files
into the plugins sub-directory of your SNAKES installation.
M. Huber and R. Lorenz: Constructing Petri Net Transducers with PNT"ooL 341
e:y/0.25
p2 t2 p4
pI t1 p1
p3 t4 pF
r,t3 x:x/0.125
x:a/0.25
1 r
(a) A simple PNT N3 . (b) Language composition N3 (N1 k N2 ).
Figure 2. Some more PNTs.
References
1. R. Lorenz and M. Huber. Petri net transducers in semantic dialogue modelling. In M. Wolff,
editor, Proceedings of ”Elektronische Sprachsignalverarbeitung (ESSV)”, volume 64 of Stud-
ientexte zur Sprachkommunikation, pages 286 – 297, 2012.
2. R. Lorenz and M. Huber. Realizing the Translation of Utterances into Meanings by Petri Net
Transducers. In P. Wagner, editor, Proceedings of ”Elektronische Sprachsignalverarbeitung
(ESSV)”, volume 65 of Studientexte zur Sprachkommunikation, pages 103 – 110, 2013.
3. R. Lorenz, M. Huber, and G. Wirsching. On weighted Petri Net Transducers. In Proccedings
of ”35th International Conference on Application and Theory of Petri Nets and Concurrency”,
Lecture Notes in Computer Science. Springer, 2014.
4. F. Pommereau. The SNAKES toolkit. https://www.ibisc.univ-evry.fr/
~fpommereau/SNAKES/, 11 2013.