For the most recent entries see the Petri Nets Newsletter.

On non-decidability of reachability for timed-arc Petri nets.

Valero Ruiz, V.; Cuartero Gomez, F.; de Frutos Escrig, D.

In: Proc. 8th Int. Workshop on Petri Net and Performance Models (PNPM'99), 8-10 October 1999, Zaragoza, Spain, pages 188-196. 1999.

Abstract: Timed-arc Petri nets are not Turing powerful, because, in particular, they cannot simulate a counter with test on zero. Thus, we could think that this model does not extend significantly the expressiveness of untimed Petri nets. But this is not true; in this paper we show that the differences between them are big enough to make the reachability problem undecidable. We also define dead tokens as those that cannot be used for firing any transitions in the future and we present some particular cases where we can identify them on this kind of timed nets.

Keywords: formal models of concurrency, reachability, timed Petri nets.

Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography