ABSTRACT
Petri networks and network models are two frameworks for the compositional design of systems of interacting entities. Here we show how to combine them using the concept of a `catalyst': an entity that is neither destroyed nor created by any process it engages in. In a Petri net, a place is a catalyst if its in-degree equals its out-degree for every transition. We show how a Petri net with a chosen set of catalysts gives a network model. This network model maps any list of catalysts from the chosen set to the category whose morphisms are all the processes enabled by this list of catalysts. Applying the Grothendieck construction, we obtain a category fibered over the category whose objects are lists of catalysts. This category has as morphisms all processes enabled by some list of catalysts. While this category has a symmetric monoidal structure that describes doing processes in parallel, its fibers also have premonoidal structures that describe doing one process and then another while reusing the catalysts.
► BibTeX data
► References
[1] J. C. Baez and J. Biamonte, Quantum Techniques in Stochastic Mechanics, World Scientific, Singapore, 2018. Available as arXiv:1209.3632, DOI: https://doi.org/10.1142/10623.
https://doi.org/10.1142/10623
arXiv:1209.3632
[2] J. C. Baez, J. Foley, J. Moeller and B. Pollard, Network models. Available as arXiv:1711.00037.
arXiv:1711.00037
[3] J. C. Baez and J. Master, Open Petri nets. Available as arXiv:1808.05415.
arXiv:1808.05415
[4] J. C. Baez and B. S. Pollard, A compositional framework for reaction networks, Rev. Math. Phys. 29 (2017), 1750028. Available as arXiv:1704.02051, DOI: https://doi.org/10.1142/S0129055X17500283.
https://doi.org/10.1142/S0129055X17500283
arXiv:1704.02051
[5] J. C. Baez and M. Stay, in New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95–172. Available as arXiv:0903.0340.
arXiv:0903.0340
[6] P. Degano, J. Meseguer and U. Montanari, Axiomatizing net computations and processes, in Logic in Computer Science, 1989, IEEE, New Jersey, pp. 175–185. Available at https://www.computer.org/csdl/proceedings/lics/1989/1954/00/00039172.pdf.
https://www.computer.org/csdl/proceedings/lics/1989/1954/00/00039172.pdf
[7] U. Engberg and G. Winskel, Petri nets as models of linear logic, in Colloquium on Trees in Algebra and Programming, Springer, Berlin, 1990, pp. 147–161.
[8] F. Foltz, G. M. Kelly, and C. Lair, Algebraic categories with few monoidal biclosed structures or none, JPAA 17 (1980), 171–177, DOI: https://doi.org/10.1016/0022-4049(80)90082-1.
https://doi.org/10.1016/0022-4049(80)90082-1
[9] C. Girault and R. Valk, Petri Nets for Systems Engineering: a Guide to Modeling, Verification, and Applications, Springer, Berlin, 2013.
[10] A. Jeffrey, Premonoidal categories and a graphical view of programs, preprint, 1997. Available as http://fpl.cs.depaul.edu/ajeffrey/papers/premonA.pdf, DOI: https://doi.org/10.1016/S1571-0661(05)80688-7.
https://doi.org/10.1016/S1571-0661(05)80688-7
http://fpl.cs.depaul.edu/ajeffrey/papers/premonA.pdf
[11] R. J. van Glabbeek and G. D. Plotkin, Configuration structures, event structures and Petri nets, Theoretical Computer Science 410 (2009), 4111–4159. Available as arXiv:0912.4023, DOI: https://doi.org/10.1016/j.tcs.2009.06.014.
https://doi.org/10.1016/j.tcs.2009.06.014
arXiv:0912.4023
[12] A. Joyal and R. Street, The geometry of tensor calculus, I, Adv. Math. 88 (1991), 55–112, DOI: https://doi.org/10.1016/0001-8708(91)90003-P.
https://doi.org/10.1016/0001-8708(91)90003-P
[13] J. Master, Generalized Petri nets. Available as arXiv:1904.09091.
arXiv:1904.09091
[14] J. Meseguer and U. Montanari, Petri nets are monoids, Information and Computation 88 (1990), 105–155, DOI: https://doi.org/10.1016/0890-5401(90)90013-8.
https://doi.org/10.1016/0890-5401(90)90013-8
[15] J. Moeller and C. Vasilakopoulou, Monoidal Grothendieck construction. Available as arXiv:1809.00727.
arXiv:1809.00727
[16] J. Moeller, Noncommutative network models. Available as arXiv:1804.07402.
arXiv:1804.07402
[17] R. E. Møgelberg and S. Staton, Linear usage of state, Logical Methods in Computer Science 10 (2014), lmcs:743. Also available as arXiv:1403.1477.
arXiv:1403.1477
[18] J. L. Peterson, Petri Net Theory and the Modeling of Systems, Prentice–Hall, New Jersey, 1981.
[19] J. Power and E. Robinson, Premonoidal categories and notions of computation, Math. Str. Comp. Sci., 7 (1997), 453–468, DOI: https://doi.org/10.1017/S0960129597002375.
https://doi.org/10.1017/S0960129597002375
[20] V. Sassone, Strong concatenable processes: an approach to the category of Petri net computations, BRICS Report Series, Dept. of Computer Science, U. Aarhus, 1994. Available at https://tidsskrift.dk/brics/article/view/ 21610/19059, DOI: https://doi.org/10.7146/brics.v1i33.21610.
https://doi.org/10.7146/brics.v1i33.21610
https://tidsskrift.dk/brics/article/view/21610/19059
[21] V. Sassone, On the category of Petri net computations, in Colloquium on Trees in Algebra and Programming, Springer, Berlin, 1995. Available at https://eprints.soton.ac.uk/261951/1/strong-conf.pdf, DOI: https://doi.org/10.7146/brics.v1i33.21610.
https://doi.org/10.7146/brics.v1i33.21610
https://eprints.soton.ac.uk/261951/1/strong-conf.pdf
[22] V. Sassone, An axiomatization of the algebra of Petri net concatenable processes, in Theoretical Computer Science 170 (1996), 277–296. Available at https://eprints.soton.ac.uk/261820/1/P-of-N-Off.pdf, DOI: https://doi.org/10.1016/S0304-3975(96)80709-2.
https://doi.org/10.1016/S0304-3975(96)80709-2
https://eprints.soton.ac.uk/261820/1/P-of-N-Off.pdf
[23] V. Sassone and P. Sobociński, A congruence for Petri nets, Electronic Notes in Theoretical Computer Science 127 (2005), 107–120. Available at https://eprints.soton.ac.uk/262302/1/petriCongPNGToff.pdf, DOI: https://doi.org/10.1016/j.entcs.2005.02.008.
https://doi.org/10.1016/j.entcs.2005.02.008
https://eprints.soton.ac.uk/262302/1/petriCongPNGToff.pdf
[24] P. Selinger, A survey of graphical languages for monoidal categories, in New Structures for Physics, ed. B. Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 289–355. Available as arXiv:0908.3347, DOI: https://doi.org/10.1007/978-3-642-12821-9_4.
https://doi.org/10.1007/978-3-642-12821-9_4
arXiv:0908.3347
[25] M. Weber, Free products of higher operad algebras. Available as arXiv:0909.4722.
arXiv:0909.4722
Cited by
[1] James Hefford and Mario Román, "Optics for Premonoidal Categories", Electronic Proceedings in Theoretical Computer Science 397, 152 (2023).
[2] Fabrizio Genovese, Fosco Loregian, and Daniele Palombi, Lecture Notes in Computer Science 12741, 185 (2021) ISBN:978-3-030-78945-9.
[3] James Hefford and Aleks Kissinger, "On the Pre- and Promonoidal Structure of Spacetime", Electronic Proceedings in Theoretical Computer Science 380, 284 (2023).
[4] John D. Foley, Spencer Breiner, Eswaran Subrahmanian, and John M. Dusel, "Operads for complex system design specification, analysis and synthesis", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 477 2250, 20210099 (2021).
The above citations are from Crossref's cited-by service (last updated successfully 2024-04-24 04:31:16). The list may be incomplete as not all publishers provide suitable and complete citation data.
On SAO/NASA ADS no data on citing works was found (last attempt 2024-04-24 04:31:16).
This Paper is published in Compositionality under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.