On the finite containment problem for Petri nets

DOI10.1016/0304-3975(86)90169-6zbMath0614.68047OpenAlexW1985986492MaRDI QIDQ1819937

Peter Clote

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90169-6

zbMATH Keywords

Ackermann functionfinite Ramsey theoremvector addition systemsfinite containment problemKarp-Miller-covering-tree

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) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ Completeness results for conflict-free vector replacement systems ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ Decision problems for propositional linear logic ⋮ Multiply-Recursive Upper Bounds with Higman’s Lemma ⋮ Linearizing well quasi-orders and bounding the length of bad sequences ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Complexity Hierarchies beyond Elementary

Cites Work

• Petri nets and large finite sets
• Rapidly growing Ramsey functions
• The equality problem for vector addition systems is undecidable
• The covering and boundedness problems for vector addition systems
• Parallel program schemata
• Reducibilities Among Decision Problems for HNN Groups, Vector Addition Systems and Subsystems of Peano Arithmetic
• The Complexity of the Finite Containment Problem for Petri Nets
• Unnamed Item
• Unnamed Item