ON A WAY TO ALGEBRA OF PETRI NETS: Algebra of PN Terms

Abstract.The present work is devoted to the study of a process algebra oriented towards processes in Place/Transition Nets (PTN in short). The processes are described by special kind of terms, termed here as PN terms. Since the time we have been dealing with Petri Nets some of the myths have survive. One of the myth is that Petri Nets are not very well suited for to be treated in de/compositional way [4]. Another myth is connected with an absence of non interleaved semantics of Petri Nets. Our treatment of Petri Nets in this work is aimed at disproving the myths. In the paper we introduce syntax and semantics of PN terms; we define the semantics by PT nets, and based on that two equivalence relations are defined on PN terms. The latter make a provision to validate some algebraic laws to hold on PN terms. Finally the algebra APT is defined. Keywords: Place/Transition Nets, PN terms, E-(B-)terms, Process Algebra, E-open terms, B-open terms. 1 Place/Transition Nets 1 By Place/Transition Net(PTN in short) we mean in this work a kind of Petri Net with multiple arcs, tokens without individualities and with unbounded capacities of places. We define PTN N to be a 4-tuple and P is a finite set of places T is a finite set of transitions N = (P, T, pre, post) (1) pre:P × T − → IN − preset function post: P × T − → IN − postset function all define a structure on the set P ∪ T. It is very common to represent the Petri Net by the oriented bipartite graph (Fig. 1). The following useful notations can be defined: N: t 2 p 2 p 1 p