For the most recent entries see the Petri Nets Newsletter.

Traps characterize home states in free choice systems.

Best, E.; Desel, J.; Esparza, J.

In: Theoretical Computer Science 101. 1992.

Abstract: Free choice nets are a subclass of Petri nets allowing to model concurrency and nondeterministic choice, but with the restriction that choices cannot be influced externally. Home states are ground markings which can be reached from any other reachable marking of a system. A trap is a structurally defined part of a net with the property that once it is marked (that is, carries at least one token), it will remain marked in any successor marking. The main result of this paper characterizes the home states of a live and bounded free choice system by the property that all traps are marked. This characterization leads to a polynomial-time algorithm for deciding the home state property. Other consequences include the proof that executing all parts of a net at least once necessarily leads to a home state; this has been a long standing conjecture.

Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography