The Complexity of the Finite Containment Problem for Petri Nets
From MaRDI portal
Publication:3912016
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
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
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 ⋮ 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
