Completeness results for conflict-free vector replacement systems
From MaRDI portal
Publication:1113674
DOI10.1016/0022-0000(88)90013-XzbMath0661.68061MaRDI QIDQ1113674
Rodney R. Howell, Louis E. Rosier
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
equivalence; reachability; Petri nets; NP-complete; containment; primitive recursive algorithm; \(\Pi ^ p_ 2\)-complete; conflict-free vector replacement systems
68Q25: Analysis of algorithms and problem complexity
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Related Items
Complexity results for 1-safe nets, A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded 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, Normal and sinkless Petri nets, Deciding a class of path formulas for conflict-free Petri nets, Bounded self-stabilizing 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
