zbMATH — the first resource for mathematics

Decidability questions for some dynamic properties of Petri nets. (Abstract of thesis). (English) Zbl 0682.68076
Summary: The thesis contains three main results: (1) the decidability of “relative boundedness” of a given place - that means boundedness in those reachable markings in which chosen places posses given numbers of tokens; it is a nontrivial corollary of the decidability of the well- known reachability problem, 2) the undecidability of the existence of an infinite (strongly) fair firing sequence; an alternative proof was given in [H. Carstensen; Lect. Notes Comput. Sci. 247, 396-407 (1987; Zbl 0629.68063)] independently, 3) the decidability of the existence of an infinite weakly fair firing sequence; it was an open problem in [loc. cit.] and [R. Howell, L. E. Rosier and Hsu-Chun Yen, Lect. Notes Comput. Sci. 324, 351-359 (1988; Zbl 0655.68072)].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
Full Text: EuDML