Structurally cyclic Petri nets

DOI10.2168/LMCS-11(4:15)2015MaRDI QIDQ3460419zbMATH OpenFDO

Authors Drewes Frank, Leroux Jérôme

Publication date 7 January 2016

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.08331

zbMATH Keywords

Petri netreachabilitystructural cyclicityvector addition system

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: A Petri net is structurally cyclic if every configuration is reachable from itself in one or more steps. We show that structural cyclicity is decidable in deterministic polynomial time. For this, we adapt the Kosaraju's approach for the general reachability problem for Petri nets.

Recommendations

• Reachability in cyclic extended free-choice systems
• Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable
• A structure to decide reachability in Petri nets
• Deciding Structural Liveness of Petri Nets
• scientific article; zbMATH DE number 4092785

Cited in

(9)

• Language theoretic properties of regular DAG languages
• On the structure of cycloids introduced by Carl Adam Petri
• Catching a structural bug with a flower
• Characterising Petri net solvable binary words
• scientific article; zbMATH DE number 1232238 (Why is no real title available?)
• Verification of flat FIFO systems
• Formal properties of Petri's cycloid systems
• Verification of Flat FIFO Systems
• Reachability in cyclic extended free-choice systems

This page was built for publication: Structurally cyclic Petri nets

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