The Reachability Problem for Petri Nets Is Not Elementary

DOI10.1145/3422822zbMath1499.68222OpenAlexW3118222663MaRDI QIDQ5056399

Jérôme Leroux, Filip Mazowiecki, Wojciech Czerwiński, Ranko Lazić, Sławomir Lasota

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3422822

zbMATH Keywords

Petri netsreachability problemsvector addition systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (4)

Lower bounds on the state complexity of population protocols ⋮ Multiparty half-duplex systems and synchronous communications ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ Population protocols: beyond runtime analysis

This page was built for publication: The Reachability Problem for Petri Nets Is Not Elementary