The reachability problem for Petri nets is not elementary

DOI10.1145/3313276.3316369zbMath1433.68245arXiv1809.07115OpenAlexW2963620995MaRDI QIDQ5212744

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

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.07115

zbMATH Keywords

Petri netsreachability problemsvector addition systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (28)

Unnamed Item ⋮ A lower bound for the coverability problem in acyclic pushdown VAS ⋮ PSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow Nets ⋮ Set augmented finite automata over infinite alphabets ⋮ Coverability in 2-VASS with one unary counter is in NP ⋮ Separators in continuous Petri nets ⋮ Recent advances on reachability problems for valence systems (invited talk) ⋮ Open Petri nets ⋮ Deciding Fast Termination for Probabilistic VASS with Nondeterminism ⋮ Finding cut-offs in leaderless rendez-vous protocols is easy ⋮ Leafy automata for higher-order concurrency ⋮ Directed reachability for infinite-state systems ⋮ Long-Run Average Behavior of Vector Addition Systems with States ⋮ Strategic reasoning with a bounded number of resources: the quest for tractability ⋮ A Note on C² Interpreted over Finite Data-Words ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The complexity of verifying population protocols ⋮ Towards efficient verification of population protocols ⋮ Non axiomatisability of positive relation algebras with constants, via graph homomorphisms ⋮ On Affine Reachability Problems ⋮ Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States ⋮ Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable ⋮ Coverability, Termination, and Finiteness in Recursive Petri Nets ⋮ Continuous One-counter Automata ⋮ Flat Petri nets (invited talk)

This page was built for publication: The reachability problem for Petri nets is not elementary