An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems

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

zbMATH Keywords

boundednessPetri netscomplexity of algorithmsVector addition systemsvector 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 ⋮ 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