Completeness results for conflict-free vector replacement systems

DOI10.1016/0022-0000(88)90013-XzbMath0661.68061OpenAlexW2087907688MaRDI QIDQ1113674

Louis E. Rosier, Rodney R. Howell

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90013-x

zbMATH Keywords

equivalencereachabilityPetri netsNP-completecontainmentprimitive recursive algorithm\(\Pi ^ p_ 2\)-completeconflict-free vector replacement 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)

Related Items

Bounded self-stabilizing Petri nets ⋮ Deciding a class of path formulas for conflict-free Petri nets ⋮ 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 ⋮ Complexity results for 1-safe nets ⋮ A Framework for Classical Petri Net Problems: Conservative Petri Nets as an Application ⋮ Normal and sinkless Petri nets ⋮ A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri nets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Petri nets and large finite sets
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
• 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
• A decidability theorem for a class of vector-addition systems
• The polynomial-time hierarchy
• The equality problem for vector addition systems is undecidable
• Complexity of some problems in Petri nets
• 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
• The Complexity of the Finite Containment Problem for Petri Nets
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Properties of Conflict-Free and Persistent Petri Nets
• A Bound on Solutions of Linear Integer Equalities and Inequalities