zbMATH — the first resource for mathematics

Timed-arc Petri nets vs. networks of timed automata. (English) Zbl 1128.68069
Ciardo, Gianfranco (ed.) et al., Applications and theory of Petri nets 2005. 26th international conference, ICATPN 2005, Miami, Fl., USA, June 20–25, 2005. Proceedings. Berlin: Springer (ISBN 3-540-26301-2/pbk). Lecture Notes in Computer Science 3536, 385-402 (2005).
Summary: We establish mutual translations between the classes of 1-safe timed-arc Petri nets (and its extension with testing arcs) and networks of timed automata (and its subclass where every clock used in the guard has to be reset). The presented translations are very tight (up to isomorphism of labelled transition systems with time). This provides a convenient characterization from the theoretical point of view but is not always satisfactory from the practical point of view because of the possible non-polynomial blow up in the size (in the direction from automata to nets). Hence we relax the isomorphism requirement and provide efficient (polynomial time) reductions between networks of timed automata and 1-safe timed-arc Petri nets preserving the answer to the reachability question. This makes our techniques suitable for automatic translation into a format required by tools like UPPAAL and KRONOS. A direct corollary of the presented reductions is a new PSPACE-completeness result for reachability in 1-safe timed-arc Petri nets, reusing the region/zone techniques already developed for timed automata.
For the entire collection see [Zbl 1076.68004].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q45 Formal languages and automata
CMC; TINA; Uppaal; Kronos
PDF BibTeX Cite
Full Text: DOI