For the most recent entries see the Petri Nets Newsletter.

Decidability of the Strict Reachability Problem for TPN's with Rational and Real Durations.

Valero Ruâz, V.; de Frutos Escrig, D.; Cuartero Gomez, F.

In: 5th International Workshop on Petri Nets and Performance Models, Toulouse (F) 19.-22. October 1993, pages 56-65. 1993.

Abstract: In this paper we introduce Timed Petri Nets with rational and real durations. A timed version of the reachability problem, the strict reachability problem, which imposes a time limit to reach the given marking, is represented. It is shown that both in the case of rational durations, and in that of real durations, this strict reachability problem is decidable. In the first case the result is obtained by scaling the time of the net, in such a way that all the durations of the transitions become integer. Then, a previous result of the authors, showing that the strict reachability problem is decidable for this kind of nets, is applied in order to conclude the desired result. Nevertheless, it is important to note that this application is not immediate, since even though after scaling we can suppose that all the durations are integer, time is no more discrete, and thus the firing of a transition can happen at any (rational) moment. In the second case a completely different approach is needed, since in general real durations cannot be normalized into integer durations. This consists on the counting of the passing of time in a symbolic way, and the simulation of the evolution of the original net without preserving the temporal order between the firing of the transitions, but only the causal order between them. This new idea is probably the most important contribution of the paper.

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

Back to the Petri Nets Bibliography