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

  1. Lookup NU author(s)
  2. Professor Eike Best
Author(s)Schmid HA, Best E
Series Editor(s)Shaw B
Publication type Report
Series TitleComputing Laboratory Technical Report Series
Source Publication DateFebruary 1978
Report Number114
Full text is available for this publication:
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.
InstitutionComputing Laboratory, The University of Newcastle upon Tyne
Place PublishedNewcastle upon Tyne
ActionsLink to this publication