A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri nets

DOI10.1016/0020-0190(91)90225-7zbMath0733.68060OpenAlexW1993706145MaRDI QIDQ809611

Hsu-Chun Yen

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90225-7

zbMATH Keywords

concurrencyconflict-free Petri net

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 (3)

Deciding a class of path formulas for conflict-free Petri nets ⋮ A solution to the covering problem for 1-bounded conflict-free Petri nets using linear programming ⋮ Model checking using net unfoldings

Cites Work

• Unnamed Item
• Unnamed Item
• An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
• Completeness results for conflict-free vector replacement systems
• A decidability theorem for a class of vector-addition systems
• Complexity of some problems in Petri nets
• The covering and boundedness problems for vector addition systems
• Properties of Conflict-Free and Persistent Petri Nets

This page was built for publication: A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri nets