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

DOI10.1016/0020-0190(91)90225-7MaRDI QIDQ809611zbMATH OpenOpenAlexFDO

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

Recommendations

• Mathematical Foundations of Computer Science 2003
• Linear time analysis of properties of conflict-free and general Petri nets
• Performance evaluation of concurrent systems using conflict-free and persistent Petri nets
• Deciding a class of path formulas for conflict-free Petri nets
• scientific article; zbMATH DE number 512938

Cites work

• scientific article; zbMATH DE number 4096790 (Why is no real title available?)
• scientific article; zbMATH DE number 4096792 (Why is no real title available?)
• A decidability theorem for a class of vector-addition systems
• An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
• Completeness results for conflict-free vector replacement systems
• Complexity of some problems in Petri nets
• Properties of Conflict-Free and Persistent Petri Nets
• The covering and boundedness problems for vector addition systems

Cited in

(3)

• A solution to the covering problem for 1-bounded conflict-free Petri nets using linear programming
• Model checking using net unfoldings
• Deciding a class of path formulas for conflict-free 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

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