×

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)].

MSC:
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.
PDF BibTeX XML Cite
Full Text: EuDML