Toggle Main Menu Toggle Search


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

Lookup NU author(s): Professor Eike Best



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.

Publication metadata

Author(s): Schmid HA, Best E

Series Editor(s): Shaw B

Publication type: Report

Series Title: Computing Laboratory Technical Report Series

Year: 1977

Pages: [42]

Source Publication Date: February 1978

Report Number: 114

Institution: Computing Laboratory, The University of Newcastle upon Tyne

Place Published: Newcastle upon Tyne