A Step Towards a Solution of the Liveness Problem in Petri Nets (1977)

Author(s): Schmid, H.A. and Best, E.

Abstact: This paper discusses a common basis for the definition of certain structural parts of Petri nets (""invariants"", ""siphon"", ""traps""), merely ""open paths"". The discussion gives rise to a comprehensive approach to the liveness problem which properly includes both the ""variant"" method of Lautenbach and the ""deadlock"" method of Hack Dynamicl properties of invariants, siphons and traps will be discussed. In particular, it will be shown that the question whether a siphon can be emptied completely under a given marking, forms one central problem for the solution of the liveness problem. the notion of ""equimoving system of open paths"" which leads from the filling transitions of a siphon is introduced. For the case in which equimoving systems exist, a necessary condition for a siphon to be emtyable is given. As one of the main results, a sufficient liveness condition for general Petri nets is given.