Timed-Arc Petri Nets vs. Networks of Timed Automata

Publikation: Konferencebidrag uden forlag/tidsskriftPosterForskning

25 Citationer (Scopus)

Resumé

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.
OriginalsprogEngelsk
Publikationsdato2005
DOI
StatusUdgivet - 2005
Begivenhed26th International Conference on Application and Theory of Petri Nets (ICATPN'05) - Miami, USA
Varighed: 20 jun. 200524 jun. 2005
Konferencens nummer: 26

Konference

Konference26th International Conference on Application and Theory of Petri Nets (ICATPN'05)
Nummer26
LandUSA
ByMiami
Periode20/06/200524/06/2005

Bibliografisk note

Værtspublikationsredaktører: Gianfranco Ciardo
Værtspublikationsredaktører: Philippe Darondeau
Serie: Lecture Notes in Computer Science, Springer, 3536, 0302-9743
Titel på proceedings: Proceedings of 26th International Conference on Application and Theory of Petri Nets (ICATPN'05)

Citer dette

Srba, J. (2005). Timed-Arc Petri Nets vs. Networks of Timed Automata. Poster session præsenteret på 26th International Conference on Application and Theory of Petri Nets (ICATPN'05), Miami, USA. https://doi.org/10.1007/11494744_22
Srba, Jiri. / Timed-Arc Petri Nets vs. Networks of Timed Automata. Poster session præsenteret på 26th International Conference on Application and Theory of Petri Nets (ICATPN'05), Miami, USA.
@conference{7d88f4a022c911db8514000ea68e967b,
title = "Timed-Arc Petri Nets vs. Networks of Timed Automata",
abstract = "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.",
author = "Jiri Srba",
note = "V{\ae}rtspublikationsredakt{\o}rer: Gianfranco Ciardo V{\ae}rtspublikationsredakt{\o}rer: Philippe Darondeau Serie: Lecture Notes in Computer Science, Springer, 3536, 0302-9743 Titel p{\aa} proceedings: Proceedings of 26th International Conference on Application and Theory of Petri Nets (ICATPN'05); null ; Conference date: 20-06-2005 Through 24-06-2005",
year = "2005",
doi = "10.1007/11494744_22",
language = "English",

}

Srba, J 2005, 'Timed-Arc Petri Nets vs. Networks of Timed Automata' 26th International Conference on Application and Theory of Petri Nets (ICATPN'05), Miami, USA, 20/06/2005 - 24/06/2005, . https://doi.org/10.1007/11494744_22

Timed-Arc Petri Nets vs. Networks of Timed Automata. / Srba, Jiri.

2005. Poster session præsenteret på 26th International Conference on Application and Theory of Petri Nets (ICATPN'05), Miami, USA.

Publikation: Konferencebidrag uden forlag/tidsskriftPosterForskning

TY - CONF

T1 - Timed-Arc Petri Nets vs. Networks of Timed Automata

AU - Srba, Jiri

N1 - Værtspublikationsredaktører: Gianfranco Ciardo Værtspublikationsredaktører: Philippe Darondeau Serie: Lecture Notes in Computer Science, Springer, 3536, 0302-9743 Titel på proceedings: Proceedings of 26th International Conference on Application and Theory of Petri Nets (ICATPN'05)

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1007/11494744_22

DO - 10.1007/11494744_22

M3 - Poster

ER -

Srba J. Timed-Arc Petri Nets vs. Networks of Timed Automata. 2005. Poster session præsenteret på 26th International Conference on Application and Theory of Petri Nets (ICATPN'05), Miami, USA. https://doi.org/10.1007/11494744_22