Reset nets between decidability and undecidability. (English) Zbl 0909.68124

Dufourd, C.; Finkel, A.; Schnoebelen, Ph.

Larsen, Kim G. (ed.) et al., Automata, languages and programming. 25th international colloquium, ICALP ’98. Aalborg, Denmark, July 13–17, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1443, 103-115 (1998).

Summary: We study Petri nets with Reset arcs (also Transfer and Doubling arcs) in combination with other extensions of the basic Petri net model. While Reachability is undecidable in all these extensions (indeed they are Turing powerful), we exhibit unexpected frontiers for the decidability of Termination, Coverability, Boundedness and place-Boundedness In particular, we show counter-intuitive separations between seemingly related problems. Our main theorem is the very surprising fact that boundedness is undecidable for Petri nets with Reset arcs.
For the entire collection see [Zbl 0893.00039].

MSC:

68Q85

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Keywords:

Petri nets; Reset arcs