Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-24T11:06:45.641Z Has data issue: false hasContentIssue false
  • English
  • Français

Open Petri nets

Published online by Cambridge University Press:  07 April 2020

John C. Baez Open the ORCID record for John C. Baez [Opens in a new window]  and
Jade Master Open the ORCID record for Jade Master [Opens in a new window]
John C. Baez*
Affiliation:
Department of Mathematics, University of California, Riverside, CA92521, USA
Jade Master*
Affiliation:
Department of Mathematics, University of California, Riverside, CA92521, USA
*
*Corresponding author. Emails: [email protected]; [email protected]
*Corresponding author. Emails: [email protected]; [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The reachability semantics for Petri nets can be studied using open Petri nets. For us, an “open” Petri net is one with certain places designated as inputs and outputs via a cospan of sets. We can compose open Petri nets by gluing the outputs of one to the inputs of another. Open Petri nets can be treated as morphisms of a category Open(Petri), which becomes symmetric monoidal under disjoint union. However, since the composite of open Petri nets is defined only up to isomorphism, it is better to treat them as morphisms of a symmetric monoidal double category ${\mathbb O}$ pen(Petri). We describe two forms of semantics for open Petri nets using symmetric monoidal double functors out of ${\mathbb O}$ pen(Petri). The first, an operational semantics, gives for each open Petri net a category whose morphisms are the processes that this net can carry out. This is done in a compositional way, so that these categories can be computed on smaller subnets and then glued together. The second, a reachability semantics, simply says which markings of the outputs can be reached from a given marking of the inputs.

Keywords

Double categoryopen systemoperational semanticsPetri netreachability
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 30 , Issue 3 , March 2020 , pp. 314 - 341
Creative Commons
Creative Common License - CCCreative Common License - BYCreative Common License - NCCreative Common License - SA
This is an Open Access article, distributed under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike licence (http://creativecommons.org/licenses/by-nc-sa/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the same Creative Commons licence is included and the original work is properly cited. The written permission of Cambridge University Press must be obtained for commercial re-use.
Copyright
© The Author(s) 2020. Published by Cambridge University Press

References

Baez, J. C. and Courser, K. (2018). Coarse-graining open Markov processes. Theory and Applications of Categories 33 (39) 1223–1268.Google Scholar
Baez, J. C. and Courser, K. (2019). Structured cospans. Available as arXiv:1911.04630.Google Scholar
Baez, J. C. and Pollard, B. (2017). A compositional framework for reaction networks. Reviews in Mathematical Physics 29 (09) 1750028.CrossRefGoogle Scholar
Baldan, P., Bonchi, F., Gadducci, F. and Monreale, G. V. (2015). Modular encoding of synchronous and asynchronous interactions using open Petri nets. Science of Computer Programming 109 (2015) 96–124.CrossRefGoogle Scholar
Baldan, P., Corradini, A., Ehrig, H. and Heckel, R. (2005). Compositional semantics for open Petri nets based on deterministic processes. Mathematical Structures in Computer Science 15 (1) 1–35.Google Scholar
Bruni, R., Megratti, H. C. and Montanari, U. (2011). A connector algebra for P/T nets interactions. In: Concurrency Theory (CONCUR’11), Lecture Notes in Computer Science, vol. 6901, Berlin, Springer, 312–326.Google Scholar
Bruni, R., Melgratti, H. C., Montanari, U. and Sobociński, P. (2013). A connector algebra for C/E and P/T nets’ interactions. Logical Methods in Computer Science 9 (2013) lmcs:883.CrossRefGoogle Scholar
Bruni, R., Meseguer, J. and Montanari, U. (2002). Symmetric monoidal and cartesian double categories as a semantic framework for tile logic. Mathematical Structures in Computer Science 12 (1) 53–90.CrossRefGoogle Scholar
Bruni, R., Meseguer, J., Montanari, U. and Sassone, V. (2001). Functorial models for Petri nets. Information and Computation 170 (2) 207–236.Google Scholar
Burstall, R. M. and Rydeheard, D. E. (1988) Computational Category Theory, Englewood Cliffs, Prentice Hall.Google Scholar
Clerc, F., Humphrey, H. and Panangaden, P. (2017) Bicategories of Markov processes. In: Aceto, L., Bacci, G., Bacci, G., Ingólfsdóttir, A., Legay, A. and Mardare, R. (eds.) Models, Algorithms, Logics and Tools, Lecture Notes in Computer Science, vol. 10460, Berlin, Springer, 112–124.CrossRefGoogle Scholar
Courser, K. (2017). A bicategory of decorated cospans. Theory and Applications of Categories 32 995–1027.Google Scholar
Czerwinski, W., Lasota, S., Lazic, R., Leroux, J. and Mazowiecki, F. (2018). The reachability problem for Petri nets is not elementary. Available as arXiv:1809.07115.Google Scholar
Day, B. and Street, R. (1997). Monoidal bicategories and Hopf algebroids. Advances in Mathematics 129 (1) 99–157.CrossRefGoogle Scholar
Degano, P., Meseguer, J. and Montanari, U. (1989). Axiomatizing net computations and processes. In Proceedings of the Fourth Annual Symposium on Logic in Computer Science, New Jersey, IEEE, 175–185.CrossRefGoogle Scholar
Ehresmann, C. (1963). Catégories structurées III: Quintettes et applications covariantes. Cahiers de Topologie et Géométrie Différentielle 5 (3) 1–22.Google Scholar
Ehresmann, C. (1965). Catégories et Structures, Paris, Dunod.Google Scholar
Freyd, P. J. and Kelly, G. M. (1972). Categories of continuous functors, I. Journal of Pure and Applied Algebra 2 (3) 169–191.CrossRefGoogle Scholar
Girault, C. and Valk, R. (2013). Petri Nets for Systems Engineering: a Guide to Modeling, Verification, and Applications, Berlin, Springer.Google Scholar
Gorrieri, R. (2017). Process Algebras for Petri Nets—The Alphabetization of Distributed Systems, Berlin, Springer.CrossRefGoogle Scholar
Grandis, M. and Paré, R. (1999). Limits in double categories. Cahiers de Topologie et Géométrie Différentielle 40 (3) 162–220.Google Scholar
Grandis, M. and Paré, R. (2004). Adjoints for double categories. Cahiers de Topologie et Géométrie Différentielle 45 (3) 193–240.Google Scholar
Jensen, K. and Kristensen, L. M. (2009). Coloured Petri Nets: Modelling and Validation of Concurrent Systems, Berlin, Springer.CrossRefGoogle Scholar
Lerman, E. (2018). Networks of open systems. Journal of Geometry and Physics 130 81–112.CrossRefGoogle Scholar
Lerman, E. and Spivak, D. (2016). An algebra of open continuous time dynamical systems and networks. Available as arXiv:1602.01017.Google Scholar
Leroux, J. and Schmitz, S. (2015). Demystifying reachability in vector addition systems. In: LICS’15: 30th Annual ACM/IEEE Symposium on Logic in Computer Science, New Jersey, IEEE, 56–67.CrossRefGoogle Scholar
Lipton, R. (1976). The Reachability Problem is Exponential-Space-Hard. Technical Report 62 (1), Department of Computer Science, Yale University.Google Scholar
Mac Lane, S. (1998) Categories for the Working Mathematician, Berlin, Springer.Google Scholar
Master, J. (2019). Generalized Petri nets. Available as arXiv:1904.09091Google Scholar
Mayr, E. (1984). An algorithm for the general Petri net reachability problem. SIAM Journal on Computing 13 (3) 441–460.Google Scholar
Meseguer, J. and Montanari, U. (1990). Petri nets are monoids. Information and Computation 88 (2) 105–155.CrossRefGoogle Scholar
Ngotiaoco, T. (2017). Compositionality of the Runge–Kutta method. Available as arXiv:1707.02804.Google Scholar
Peterson, J. L. (1981). Petri Net Theory and the Modeling of Systems, New Jersey, Prentice Hall.Google Scholar
Rathke, J., Sobociński, P. and Stephens, O. (2014). Compositional reachability in Petri nets. In: International Workshop on Reachability Problems, Lecture Notes in Computer Science, vol. 8762, Berlin, Springer.Google Scholar
Sassone, V. (1994). Strong concatenable processes: an approach to the category of Petri net computations. BRICS Report Series, Department of Computer Science. University of Aarhus.Google Scholar
Sassone, V. (1995). On the category of Petri net computations. In: CAAP’92: 17th Colloquium on Trees in Algebra and Programming, Lecture Notes in Computer Science, vol. 581, Berlin, Springer.Google Scholar
Sassone, V. (1996) An axiomatization of the algebra of Petri net concatenable processes. Theoretical Computer Science 170 (1–2) 277–296.CrossRefGoogle Scholar
Sassone, V. and Sobociński, P. (2005). A congruence for Petri nets. Electronic Notes in Theoretical Computer Science 127 107–120.CrossRefGoogle Scholar
Shulman, M. (2010). Constructing symmetric monoidal bicategories. Available as arXiv:1004.0993.Google Scholar
Sobociński, P. and Stephens, O. (2013). Reachability via compositionality in Petri nets. Available as arXiv:1303.1399.Google Scholar
Stay, M. (2016). Compact closed bicategories. Theory and Applications of Categories 31 (26) 755–798.Google Scholar
Trimble, T. (2009). Multisorted Lawvere theories. nLab.Google Scholar
van Glabbeek, R. J. and Plotkin, G. D. (2009). Configuration structures, event structures and Petri nets. Theoretical Computer Science 410 (41) 4111–4159.CrossRefGoogle Scholar