Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states

DOI10.1016/0304-3975(86)90026-5zbMath0633.68029OpenAlexW2001068306MaRDI QIDQ1096388

Dung T. Huynh, Louis E. Rosier, Rodney R. Howell, Hsu-Chun Yen

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)90026-5

zbMATH Keywords

Petri netsdecidabilitycomplexity analysisreachability setsequivalence problemsvector addition systemseffectively computable semilinear sets

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)

Related Items

Deciding a class of path formulas for conflict-free Petri nets ⋮ Completeness results for conflict-free vector replacement systems ⋮ Problems concerning fairness and temporal logic for conflict-free Petri nets ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ A unified approach for deciding the existence of certain petri net paths ⋮ Undecidability of bisimilarity for Petri nets and some related problems ⋮ Normal and sinkless Petri nets ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ A taxonomy of fairness and temporal logic problems for Petri nets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of the word problem for commutative semigroups of fixed dimension
• Petri nets and large finite sets
• The decidability of persistence for vector addition systems
• Vector addition systems and regular languages
• Persistence of vector replacement systems is decidable
• On the reachability problem for 5-dimensional vector addition systems
• Petri nets and regular languages
• On weak persistency of Petri nets
• A decidability theorem for a class of vector-addition systems
• The equality problem for vector addition systems is undecidable
• On the finite containment problem for Petri nets
• A multiparameter analysis of the boundedness problem for vector addition systems
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Parallel program schemata
• A note on the complexity of program evaluation
• An Algorithm for the General Petri Net Reachability Problem
• The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals
• The Complexity of the Finite Containment Problem for Petri Nets
• Alternation
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Properties of Conflict-Free and Persistent Petri Nets
• Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines