The Complexity of the Finite Containment Problem for Petri Nets

DOI10.1145/322261.322271zbMath0462.68020OpenAlexW1975261774MaRDI QIDQ3912016

Albert R. Meyer, Ernst W. Mayr

Publication date: 1981

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

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

zbMATH Keywords

inclusion problemreachability setprimitive recursive complexity

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) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (27)

Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ Unnamed Item ⋮ Completeness results for conflict-free vector replacement systems ⋮ Nonelementary Complexities for Branching VASS, MELL, and Extensions ⋮ Unnamed Item ⋮ Classifying the computational complexity of problems ⋮ Behavioural equivalence for infinite systems — Partially decidable! ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ Data flow analysis of asynchronous systems using infinite abstract domains ⋮ An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, and applications to commutative semigroups ⋮ Normal and sinkless Petri nets ⋮ Error-correcting Petri nets ⋮ Nonprimitive recursive complexity and undecidability for Petri net equivalences ⋮ The complexity of decision procedures in relevance logic II ⋮ The covering and boundedness problems for vector addition systems ⋮ Unnamed Item ⋮ Ackermannian completion of separators ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems ⋮ On the finite containment problem for Petri nets ⋮ Complexity Hierarchies beyond Elementary ⋮ The complexity of the word problems for commutative semigroups and polynomial ideals ⋮ Verifying lossy channel systems has nonprimitive recursive complexity. ⋮ Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups. ⋮ Petri nets and large finite sets ⋮ Flat Petri nets (invited talk) ⋮ Synchronizing sequences on a class of unbounded systems using synchronized Petri nets

This page was built for publication: The Complexity of the Finite Containment Problem for Petri Nets