Abstract
We define an algebraic framework based on non-safe Petri nets, which allows one to express operations such as iteration, parallel composition, and transition synchronisation. This leads to an algebra of process expressions, whose constants and operators directly correspond to those used in Petri nets, and so we are able to associate nets to process expressions compositionally. The semantics of composite nets is then used to guide the definition of a structured operational semantics of process expressions. The main result is that an expression and the corresponding net generate isomorphic transition systems. We finally discuss a partial order semantics of the two algebras developed in this paper.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
T. Basten and M. Voorhoeve: An Algebraic Semantics for Hierarchical P/T Nets. ICATPN’95, Springer, LNCS 935 (1995) 45–65.
E. Best and R. Devillers: Sequential and Concurrent Behaviour in Petri Net Theory. Theoretical Computer Science 55 (1988) 87–136.
E. Best, R. Devillers and J. Hall: The Petri Box Calculus: a New Causal Algebra with Multilabel Communication. In: Advances in Petri Nets 1992, G. Rozenberg (Ed.). Springer, LNCS 609 (1992) 21–69.
E. Best, R. Devillers and M. Koutny: Petri Net Algebra. EATCS Monographs on TCS, Springer (2001).
G. Boudol and I. Castellani: Flow Models of Distributed Computations: Three Equivalent Semantics for CCS. Information and Computation 114 (1994) 247–314.
P. Degano, R. De Nicola and U. Montanari: A Distributed Operational Semantics for CCS Based on C/E Systems. Acta Informatica 26 (1988) 59–91.
R. Devillers, H. Klaudel, M. Koutny, E. Pelz and F. Pommereau: Operational Semantics for PBC with Asynchronous Communication. HPC’02, SCS (2002) 314–319.
R. Devillers, H. Klaudel, M. Koutny and F. Pommereau: Asynchronous Box Calculus. Technical Report CS-TR-759, Dept. of Comp. Sci., Univ. of Newcastle (2002).
J. Esparza, S. Römer and W. Vogler: An Improvement of McMillan’s Unfolding Algorithm. TACAS’96, Springer, LNCS 1055 (1996) 87–106.
R. J. van Glabbeek and F. V. Vaandrager: Petri Net Models for Algebraic Theories of Concurrency. PARLE’87, Springer, LNCS 259 (1987) 224–242.
U. Goltz and R. Loogen: A Non-interleaving Semantic Model for Nondeterministic Concurrent Processes. Fundamentae Informaticae 14 (1991) 39–73.
R. Gorrieri and U. Montanari: On the Implementation of Concurrent Calculi in Net Calculi: two Case Studies. Theoretical Computer Science 141(1–2) (1995) 195–252.
C. A. R. Hoare: Communicating Sequential Processes. Prentice Hall (1985).
P. W. Hoogers, H. C. M. Kleijn and P. S. Thiagarajan: An Event Structure Semantics for General Petri Nets. Theoretical Computer Science 153 (1996) 129–170.
H. Klaudel and F. Pommereau: Asynchronous links in the PBC and M-nets. ASIAN’99, Springer, LNCS 1742 (1999) 190–200.
H. Klaudel and F. Pommereau: A concurrent and Compositional Petri Net Semantics of Preemption. IFM’2000, Springer, LNCS 1945 (2000) 318–337.
R. Milner: Communication and Concurrency. Prentice Hall (1989).
E. R. Olderog: Nets, Terms and Formulas. Cambridge Tracts in Theoretical Computer Science 23, Cambridge University Press (1991).
G. D. Plotkin: A Structural Approach to Operational Semantics. Technical Report FN-19, Computer Science Department, University of Aarhus (1981).
W. Reisig: Petri Nets. An Introduction. EATCS Monographs, Springer (1985).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Devillers, R., Klaudel, H., Koutny, M., Pommereau, F. (2002). An Algebra of Non-safe Petri Boxes. In: Kirchner, H., Ringeissen, C. (eds) Algebraic Methodology and Software Technology. AMAST 2002. Lecture Notes in Computer Science, vol 2422. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45719-4_14
Download citation
DOI: https://doi.org/10.1007/3-540-45719-4_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44144-1
Online ISBN: 978-3-540-45719-0
eBook Packages: Springer Book Archive