{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T06:24:36Z","timestamp":1773901476541,"version":"3.50.1"},"reference-count":43,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"content-version":"unspecified","delay-in-days":37,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The reachability semantics for Petri nets can be studied using open Petri nets. For us, an \u201copen\u201d 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 <jats:italic>double<\/jats:italic> category <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0960129520000043_inline1.png\"\/><jats:tex-math>\n${\\mathbb O}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:bold>pen<\/jats:bold>(Petri). We describe two forms of semantics for open Petri nets using symmetric monoidal double functors out of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0960129520000043_inline1.png\"\/><jats:tex-math>\n${\\mathbb O}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:bold>pen<\/jats:bold>(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.<\/jats:p>","DOI":"10.1017\/s0960129520000043","type":"journal-article","created":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T06:30:54Z","timestamp":1586241054000},"page":"314-341","source":"Crossref","is-referenced-by-count":34,"title":["Open Petri nets"],"prefix":"10.1017","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0609-9836","authenticated-orcid":false,"given":"John C.","family":"Baez","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1970-6030","authenticated-orcid":false,"given":"Jade","family":"Master","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,4,7]]},"reference":[{"key":"S0960129520000043_ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.014"},{"key":"S0960129520000043_ref2","unstructured":"Baez, J. C. and Courser, K. (2019). Structured cospans. Available as arXiv:1911.04630."},{"key":"S0960129520000043_ref38","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.02.008"},{"key":"S0960129520000043_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)80709-2"},{"key":"S0960129520000043_ref35","volume-title":"BRICS Report Series","author":"Sassone","year":"1994"},{"key":"S0960129520000043_ref29","unstructured":"Master, J. (2019). Generalized Petri nets. Available as arXiv:1904.09091"},{"key":"S0960129520000043_ref33","volume-title":"Petri Net Theory and the Modeling of Systems","author":"Peterson","year":"1981"},{"key":"S0960129520000043_ref41","first-page":"755","article-title":"Compact closed bicategories","volume":"31","author":"Stay","year":"2016","journal-title":"Theory and Applications of Categories"},{"key":"S0960129520000043_ref10","volume-title":"Computational Category Theory","author":"Burstall","year":"1988"},{"key":"S0960129520000043_ref26","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.16"},{"key":"S0960129520000043_ref25","unstructured":"Lerman, E. and Spivak, D. (2016). An algebra of open continuous time dynamical systems and networks. Available as arXiv:1602.01017."},{"key":"S0960129520000043_ref39","unstructured":"Shulman, M. (2010). Constructing symmetric monoidal bicategories. Available as arXiv:1004.0993."},{"key":"S0960129520000043_ref15","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1989.39172"},{"key":"S0960129520000043_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129501003462"},{"key":"S0960129520000043_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/b95112"},{"key":"S0960129520000043_ref9","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1006\/inco.2001.3050","article-title":"Functorial models for Petri nets","volume":"170","author":"Bruni","year":"2001","journal-title":"Information and Computation"},{"key":"S0960129520000043_ref6","first-page":"312","volume-title":"Concurrency Theory (CONCUR\u201911)","author":"Bruni","year":"2011"},{"key":"S0960129520000043_ref13","unstructured":"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."},{"key":"S0960129520000043_ref28","volume-title":"Categories for the Working Mathematician","author":"Mac Lane","year":"1998"},{"key":"S0960129520000043_ref36","volume-title":"CAAP\u201992: 17th Colloquium on Trees in Algebra and Programming","author":"Sassone","year":"1995"},{"key":"S0960129520000043_ref34","volume-title":"International Workshop on Reachability Problems","author":"Rathke","year":"2014"},{"key":"S0960129520000043_ref27","unstructured":"Lipton, R. (1976). The Reachability Problem is Exponential-Space-Hard. Technical Report 62 (1), Department of Computer Science, Yale University."},{"key":"S0960129520000043_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-55559-1"},{"key":"S0960129520000043_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90013-8"},{"key":"S0960129520000043_ref1","first-page":"1223","article-title":"Coarse-graining open Markov processes","volume":"33","author":"Baez","year":"2018","journal-title":"Theory and Applications of Categories"},{"key":"S0960129520000043_ref30","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1137\/0213029","article-title":"An algorithm for the general Petri net reachability problem","volume":"13","author":"Mayr","year":"1984","journal-title":"SIAM Journal on Computing"},{"key":"S0960129520000043_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2014.11.019"},{"key":"S0960129520000043_ref17","volume-title":"Cat\u00e9gories et Structures","author":"Ehresmann","year":"1965"},{"key":"S0960129520000043_ref12","first-page":"995","article-title":"A bicategory of decorated cospans","volume":"32","author":"Courser","year":"2017","journal-title":"Theory and Applications of Categories"},{"key":"S0960129520000043_ref19","volume-title":"Petri Nets for Systems Engineering: a Guide to Modeling, Verification, and Applications","author":"Girault","year":"2013"},{"key":"S0960129520000043_ref22","first-page":"193","article-title":"Adjoints for double categories","volume":"45","author":"Grandis","year":"2004","journal-title":"Cahiers de Topologie et G\u00e9om\u00e9trie Diff\u00e9rentielle"},{"key":"S0960129520000043_ref3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129055X17500283"},{"key":"S0960129520000043_ref40","unstructured":"Soboci\u0144ski, P. and Stephens, O. (2013). Reachability via compositionality in Petri nets. Available as arXiv:1303.1399."},{"key":"S0960129520000043_ref7","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(3:16)2013"},{"key":"S0960129520000043_ref21","first-page":"162","article-title":"Limits in double categories","volume":"40","author":"Grandis","year":"1999","journal-title":"Cahiers de Topologie et G\u00e9om\u00e9trie Diff\u00e9rentielle"},{"key":"S0960129520000043_ref14","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1997.1649"},{"key":"S0960129520000043_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63121-9_6"},{"key":"S0960129520000043_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.geomphys.2018.03.020"},{"key":"S0960129520000043_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(72)90001-1"},{"key":"S0960129520000043_ref16","first-page":"1","article-title":"Cat\u00e9gories structur\u00e9es III: Quintettes et applications covariantes","volume":"5","author":"Ehresmann","year":"1963","journal-title":"Cahiers de Topologie et G\u00e9om\u00e9trie Diff\u00e9rentielle"},{"key":"S0960129520000043_ref5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0960129504004311","article-title":"Compositional semantics for open Petri nets based on deterministic processes","volume":"15","author":"Baldan","year":"2005","journal-title":"Mathematical Structures in Computer Science"},{"key":"S0960129520000043_ref32","unstructured":"Ngotiaoco, T. (2017). Compositionality of the Runge\u2013Kutta method. Available as arXiv:1707.02804."},{"key":"S0960129520000043_ref42","unstructured":"Trimble, T. (2009). Multisorted Lawvere theories. nLab."}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129520000043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,13]],"date-time":"2020-04-13T09:15:16Z","timestamp":1586769316000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129520000043\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["S0960129520000043"],"URL":"https:\/\/doi.org\/10.1017\/s0960129520000043","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3]]}}}