Timed-Arc Petri Nets vs. Networks of Timed Automata
SRBA, Jiří. Timed-Arc Petri Nets vs. Networks of Timed Automata. In Proceedings of the 26th International Conference on Application and Theory of {P}etri Nets (ICATPN 2005). Netherlands: Springer-Verlag, 2005, s. 385-402. |
Další formáty:
BibTeX
LaTeX
RIS
|
Základní údaje | |
---|---|
Originální název | Timed-Arc Petri Nets vs. Networks of Timed Automata |
Název česky | Casove Petriho site vs. site casovych automatu |
Autoři | SRBA, Jiří (203 Česká republika, garant). |
Vydání | Netherlands, Proceedings of the 26th International Conference on Application and Theory of {P}etri Nets (ICATPN 2005), od s. 385-402, 18 s. 2005. |
Nakladatel | Springer-Verlag |
Další údaje | |
---|---|
Originální jazyk | angličtina |
Typ výsledku | Stať ve sborníku |
Obor | 10201 Computer sciences, information science, bioinformatics |
Stát vydavatele | Nizozemské království |
Utajení | není předmětem státního či obchodního tajemství |
Kód RIV | RIV/00216224:14330/05:00012754 |
Organizační jednotka | Fakulta informatiky |
UT WoS | 000230367400022 |
Klíčová slova anglicky | Petri nets; time models; verification; timed automata |
Štítky | Petri nets, time models, timed automata, verification |
Změnil | Změnil: RNDr. JUDr. Vladimír Šmíd, CSc., učo 1084. Změněno: 6. 7. 2007 09:02. |
Anotace |
---|
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. |
Anotace česky |
---|
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. |
Návaznosti | |
---|---|
GA201/03/1161, projekt VaV | Název: Verifikace nekonečně stavových systémů |
Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů | |
MSM0021622419, záměr | Název: Vysoce paralelní a distribuované výpočetní systémy |
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy | |
1M0545, projekt VaV | Název: Institut Teoretické Informatiky |
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky |
VytisknoutZobrazeno: 17. 8. 2024 20:36