Detailed Information on Publication Record
2005
Timed-Arc Petri Nets vs. Networks of Timed Automata
SRBA, JiříBasic information
Original name
Timed-Arc Petri Nets vs. Networks of Timed Automata
Name in Czech
Casove Petriho site vs. site casovych automatu
Authors
SRBA, Jiří (203 Czech Republic, guarantor)
Edition
Netherlands, Proceedings of the 26th International Conference on Application and Theory of {P}etri Nets (ICATPN 2005), p. 385-402, 18 pp. 2005
Publisher
Springer-Verlag
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Netherlands
Confidentiality degree
není předmětem státního či obchodního tajemství
RIV identification code
RIV/00216224:14330/05:00012754
Organization unit
Faculty of Informatics
UT WoS
000230367400022
Keywords in English
Petri nets; time models; verification; timed automata
Změněno: 6/7/2007 09:02, RNDr. JUDr. Vladimír Šmíd, CSc.
V originále
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.
In Czech
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.
Links
| GA201/03/1161, research and development project |
| ||
| MSM0021622419, plan (intention) |
| ||
| 1M0545, research and development project |
|