×

Decidability questions for fairness in Petri nets. (English) Zbl 0629.68063

STACS 87, Theoretical aspects of computer science, Proc. 4th annu. Symp., Passau/FRG 1987, Lect. Notes Comput. Sci. 247, 396-407 (1987).
[For the entire collection see Zbl 0604.00016.]
The infinite and fair behaviour of Petri nets is investigated. A fair behaviour of some Petri net is given by an infinite transition (or firing) sequence v in which every transition which is activated infinitely often also occurs infinitely often. It is shown that the existence of a fair transition sequence in a given Petri net is undecidable. The criterion for justice or weak fairness, here called the finite delay property for a group of transitions is shown to be decidable. The results extend those of G. W. Brams [Réseaux de Petri: théorie et pratique. Tome 1: Théorie et analyse (1983; Zbl 0501.68027)] and H. Carstensen and R. Valk [Lect. Notes Comput. Sci. 188, 83-100 (1985; Zbl 0571.68045)].
Reviewer: M.Jantzen

MSC:

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