A polynomial-time algorithm to decide liveness of bounded free choice nets

DOI10.1016/0304-3975(92)90299-UzbMath0776.68090MaRDI QIDQ1193656

S. Singh

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

livenessPetri netspolynomial time algorithmbounded free choice netslinear algebraic calculation of deadlocks and traps

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

Reachability in live and safe free-choice Petri nets is NP-complete ⋮ On liveness in Extended Non Self-Controlling Nets ⋮ Linear time analysis of properties of conflict-free and general Petri nets ⋮ On liveness and controlled siphons in Petri nets ⋮ Complexity results for 1-safe nets ⋮ Structure theory of equal conflict systems ⋮ Notes on liveness and boundedness of extended strong asymmetric choice nets. II

Cites Work

• Partial order behaviour and structure of Petri nets
• A polynomial Newton method for linear programming
• Complexity of some problems in Petri nets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A polynomial-time algorithm to decide liveness of bounded free choice nets