Structural Liveness of Immediate Observation Petri Nets

• Autorzy: Jančar Petr , Valůšek Jiří

Identyfikatory

DOI

10.3233/FI-222146

• Języki publikacji: EN

Abstrakty

EN

We look in detail at the structural liveness problem (SLP) for subclasses of Petri nets, namely immediate observation nets (IO nets) and their generalized variant called branching immediate multi-observation nets (BIMO nets), that were recently introduced by Esparza, Raskin, and Weil-Kennedy. We show that SLP is PSPACE-hard for IO nets and in PSPACE for BIMO nets. In particular, we discuss the (small) bounds on the token numbers in net places that are decisive for a marking to be (non)live.

Słowa kluczowe

EN

Petri nets; immediate observation nets; structural liveness; complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 188, nr 3
• Strony: 179--215
• Opis fizyczny: Bibliogr. xx poz.

Twórcy

autor

Jančar Petr

• Dept of Computer Science, Faculty of Science Palack´y University in Olomouc Czech Republic

autor

Valůšek Jiří

• Dept of Computer Science, Faculty of Science Palack´y University in Olomouc Czech Republic

Bibliografia

• [1] Leroux J, Schmitz S. Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension. In: 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019. IEEE, 2019 pp. 1-13. doi:10.1109/LICS.2019.8785796.
• [2] Leroux J. The Reachability Problem for Petri Nets is Not Primitive Recursive. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. IEEE, 2021 pp. 1241-1252. doi:10.1109/FOCS52979.2021.00121.
• [3] Czerwinski W, Orlikowski L. Reachability in Vector Addition Systems is Ackermann-complete. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. IEEE, 2021 pp. 1229-1240. doi:10.1109/FOCS52979.2021.00120.
• [4] Hack M. Decidability questions for Petri Nets. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1976. URL http://hdl.handle.net/1721.1/27441.
• [5] Best E, Esparza J. Existence of home states in Petri nets is decidable. Inf. Process. Lett., 2016. 116(6):423-427. doi:10.1016/j.ipl.2016.01.011.
• [6] Jančar P, Purser D. Structural liveness of Petri nets is ExpSpace-hard and decidable. Acta Informatica, 2019. 56(6):537-552. doi:10.1007/s00236-019-00338-6.
• [7] Esparza J, Raskin MA, Weil-Kennedy C. Parameterized Analysis of Immediate Observation Petri Nets. In: Application and Theory of Petri Nets and Concurrency - 40th International Conference, PETRI NETS 2019, Aachen, Germany, June 23-28, 2019, Proceedings, volume 11522 of Lecture Notes in Computer Science. Springer, 2019 pp. 365-385. doi:10.1007/978-3-030-21571-2\ 20. An extended version at https://arxiv.org/abs/1902.03025.
• [8] Raskin M, Weil-Kennedy C. Efficient Restrictions of Immediate Observation Petri Nets. In: Reachability Problems - 14th International Conference, RP 2020, Paris, France, October 19-21, 2020, Proceedings, volume 12448 of Lecture Notes in Computer Science. Springer, 2020 pp. 99-114. doi:10.1007/978-3-030-61739-4\7.
• [9] Raskin MA, Weil-Kennedy C, Esparza J. Flatness and Complexity of Immediate Observation Petri Nets. In: 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference), volume 171 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2020 pp. 45:1-45:19. doi:10.4230/LIPIcs.CONCUR.2020.45.
• [10] Angluin D, Aspnes J, Diamadi Z, Fischer MJ, Peralta R. Computation in networks of passively mobile finite-state sensors. Distributed Comput., 2006. 18(4):235-253. doi:10.1007/s00446-005-0138-3.
• [11] Angluin D, Aspnes J, Eisenstat D, Ruppert E. The computational power of population protocols. Distributed Comput., 2007. 20(4):279-304. doi:10.1007/s00446-007-0040-2.
• [12] Esparza J. Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes. Fundam. Informaticae, 1997. 31(1):13-25. doi:10.3233/FI-1997-3112.
• [13] Jones ND, Landweber LH, Lien YE. Complexity of Some Problems in Petri Nets. Theor. Comput. Sci., 1977. 4(3):277-299. Doi:10.1016/0304-3975(77)90014-7.
• [14] Jančar P, Leroux J, Val˚usek J. Structural Liveness of (Conservative and General) Petri Nets. (in preparation).
• [15] Desel J, Esparza J. Free Choice Petri Nets. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1995. doi:10.1017/CBO9780511526558.