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

DOI10.1016/0020-0190(87)90089-5MaRDI QIDQ1097037zbMATH OpenOpenAlexFDO

Authors Rodney R. Howell, Louis E. Rosier, Hsu-Chun Yen

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)

Recommendations

• A multiparameter analysis of the boundedness problem for vector addition systems
• Completeness results for conflict-free vector replacement systems
• scientific article; zbMATH DE number 4037227
• scientific article; zbMATH DE number 4024808
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states

Cites work

• A decidability theorem for a class of vector-addition systems
• A multiparameter analysis of the boundedness problem for vector addition systems
• Complete problems for deterministic polynomial time
• Complexity of some problems in Petri nets
• Complexity of the word problem for commutative semigroups of fixed dimension
• Depth-First Search and Linear Graph Algorithms
• Parallel program schemata
• Properties of Conflict-Free and Persistent Petri Nets
• The covering and boundedness problems for vector addition systems

Cited in

(11)

• A multiparameter analysis of the boundedness problem for vector addition systems
• Completeness results for conflict-free vector replacement systems
• scientific article; zbMATH DE number 4024808 (Why is no real title available?)
• Bounded self-stabilizing Petri nets
• Normal and sinkless 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 solution to the covering problem for 1-bounded conflict-free Petri nets using linear programming
• Deciding a class of path formulas for conflict-free Petri nets
• Linear time analysis of properties of conflict-free and general Petri nets
• A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri nets

This page was built for publication: An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097037)