zbMATH — the first resource for mathematics

Infinite behaviour and fairness in Petri nets. (English) Zbl 0571.68045
Advances in Petri nets 1984, Lect. Notes Comput. Sci. 188, 83-100 (1985).
[For the entire collection see Zbl 0556.00014.]
Languages of labelled infinite firing sequences of Petri nets, called \(\omega\)-behaviours, are investigated. Several definitions of \(\omega\)- behaviours are given and their descriptive power is compared. First we give an overview of the results on i-behaviour and bounded i-behaviour with \(i\in \{1,1',2,2',3\}\) of Petri nets as described by the second author [Theor. Comput. Sci. 25, 311-341 (1983; Zbl 0559.68057)]. These \(\omega\)-behaviours were defined by markings on all places, respectively only on bounded places, in five different ways. E.g. 3-behaviour requires that exactly the designated markings are visited infinitely often. Here we introduce similar definitions on the transitions used for the infinite firing sequences. It can be shown that the classes of transitional i- behaviours are equal to the classes of bounded i-behaviours.
An \(\omega\)-behaviour of some net may be called fair, either if all or a designated set of transitions must appear infinitely often or if the firing rule is fair. These fairness criteria are called problem and execution fairness, respectively. Problem fairness may be described by transitional i-behaviour of nets. For execution fairness we give two definitions. A sequence is called just, if for every transition there are infinitely many situations so that it is inactive or it fires. And a sequence is fair, if every infinitely often activated transition fires infinitely often. It is shown that the class of just behaviours of Petri nets includes all classes of i- and transitional i-behaviours, and itself it is strictly included in the class of fair behaviours. The proofs are constructive, i.e., for some transitional i-behaviour a construction for a net is given which has the same just behaviour.

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q45 Formal languages and automata