An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
From MaRDI portal
Publication:1097037
DOI10.1016/0020-0190(87)90089-5zbMath0634.68058OpenAlexW2034917600MaRDI QIDQ1097037
Hsu-Chun Yen, Louis E. Rosier, Rodney R. Howell
Publication date: 1987
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(87)90089-5
Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Related Items (9)
Bounded self-stabilizing Petri nets ⋮ 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 ⋮ Linear time analysis of properties of conflict-free and general Petri nets ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ A solution to the covering problem for 1-bounded conflict-free Petri nets using linear programming ⋮ Normal and sinkless Petri nets ⋮ A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri nets
Cites Work
- Complexity of the word problem for commutative semigroups of fixed dimension
- A decidability theorem for a class of vector-addition systems
- Complete problems for deterministic polynomial time
- Complexity of some problems in Petri nets
- The covering and boundedness problems for vector addition systems
- A multiparameter analysis of the boundedness problem for vector addition systems
- Parallel program schemata
- Properties of Conflict-Free and Persistent Petri Nets
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
