Liveness Criteria for Special Classes of Nets

(a) Free Choice Nets

1. M Hack: Corrections to “Analysis of Production Schemata by Petri Nets”. Computation Structures Group Note 17, Project MAC (June 1974). In [7], Hack proves the deadlock/trap criterion for the liveness of free choice nets. Our proof is a slight modification of his. Further studies on free choice nets include:

   Google Scholar 

2. E. Best, M. W. Shields: Some Equivalence Results for Free Choice Nets and Simple Nets and on the Periodicity of Live Free Choice Nets. Preprint of CAAP 83, 8th Colloquium on Trees in Algebra and Programming, L’Aquila. Lecture Notes in Computer Science 159, Springer-Verlag (1983), pp. 141–154

   Google Scholar 

3. K. Döpp: Zum Hackschen Wohlformungssatz für Free-Choice-Petrinetze. EIK 19, 1/2 (1983), pp. 3–15 Generalizations of the liveness criterion for free choice nets are found in the following two papers:

   MATH  Google Scholar 

4. M. Hack: Extended State Machine Allocatable Nets (ESMA), an Extension of Free Choice Petri Nets Results, Computation Structures Group Memo 78, Project MAC, MIT Cambridge, Massachusetts (1973), revised as Memo 78–1 (1974)

   Google Scholar 

5. W. Griese: Liveness in NSC-Petri Nets, in: Discrete Structures and Algorithms, U. Pape (ed.), Carl Hanser Verlag, München (1980)

   Google Scholar 

6. P. S. Thiagarajan, K. Voss: A Fresh Look at Free Choice Nets. Arbeitspapiere der GMD, Nr. 58, October 1983

   Google Scholar 

7. E. Best, K. Voss: Free Choice Systems have Home States. Acta Informatica 21 (1984), pp. 89–100 Similar results on further net classes are discussed in [47]. “Bipolar Schemata” may be considered as a special class of free choice nets:

   Article  MathSciNet  Google Scholar 

8. H. J. Genrich, P. S. Thiagarajan: A Theory for Bipolar Synchronization Schemes. Theoretical Computer Science 30 (1984), pp. 241–318 They are also mentioned in [29].

   Article  MathSciNet  MATH  Google Scholar 

(b) Marked Graphs

1. H. Genrich: Das Zollstationenproblem. Internal Reports GMD-I5/69–01–15 and /71–10–13, Gesellschaft für Mathematik und Datenverarbeitung, Bonn (1969 and 1971),

   Google Scholar 

2. A. W. Holt, F. Commoner: Events & Conditions. Applied Data Research, New York (1970).Our proofs in Chap. 7.3 are taken from Genrich’s paper [109]. More detailed investigations are given in [57] and in the following papers:

   Google Scholar 

3. F. Commoner, A. W. Holt, S. Even, A. Pnueli: Marked Directed Graphs. Journal of Computer and System Sciences 5 (1971), pp. 511–523

   Article  MathSciNet  MATH  Google Scholar 

4. H. J. Genrich, K. Lautenbach: Synchronisationsgraphen. Acta Informatica 2 (1973), pp. 143–161.

   Article  MathSciNet  MATH  Google Scholar 

(c) Further Net Classes

1. O. Herzog: Static Analysis of Concurrent Processes for Dynamic Properties Using Petri Nets. Lecture Notes in Computer Science 70, Springer-Verlag (1980)

   Google Scholar 

2. W. Reisig: Deterministic Buffer Synchronization of Sequential Processes. Acta Informatica 18 (1982), pp. 117–134

   Article  MathSciNet  MATH  Google Scholar 

3. K. Lautenbach, P. S. Thiagarajan: Analysis of a Resource Allocation Problem Using Petri Nets. First European Conference on Distributed Processing, Toulouse, J. Syre (ed.), 1979, pp. 260–266

   Google Scholar 

4. F. De Cindio, G. de Michelis, L. Pomello, C. Simone: Superposed Automata Nets, in [18].There have been investigations trying to find net classes with more or less simple decision procedures for liveness. [8] introduced a class called “simple”. They are also studied in [104]. Landweber and Robertson [53] consider “conflict free” nets.

   Google Scholar 

Download references