
When are Timed Automata Weakly Timed Bisimilar to Time Petri Nets?
Roux, Olivier-Henri; Lime, Didier; Haddad, Serge; Cassez, Franck; Bérard, Béatrice (2005), When are Timed Automata Weakly Timed Bisimilar to Time Petri Nets?, in Sen, Sandeep; Ramanujam, R., FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings, Springer : Berlin, p. 273-284. http://dx.doi.org/10.1007/11590156_22
View/ Open
Type
Communication / ConférenceDate
2005Conference title
FSTTCS 2005 25th International Conference on Foundations of Software Technology and Theoretical Computer ScienceConference date
2005-12Conference city
HyderabadConference country
IndeBook title
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science 25th International Conference, Hyderabad, India, December 15-18, 2005, ProceedingsBook author
Sen, Sandeep; Ramanujam, R.Publisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
3821Published in
Berlin
ISBN
978-3-540-30495-1
Number of pages
566Pages
273-284
Publication identifier
Metadata
Show full item recordAbstract (EN)
In this paper, we compare Timed Automata (TA) with Time Petri Nets (TPN) with respect to weak timed bisimilarity. It is already known that the class of bounded TPNs is included in the class of TA. It is thus natural to try and identify the (strict) subclass ${\cal TA}^{wtb}$ of TA that is equivalent to TPN for the weak time bisimulation relation. We give a characterisation of this subclass and we show that the membership problem and the reachability problem for ${\cal TA}^{wtb}$ are PSPACE-complete. Furthermore we show that for a TA in ${\cal TA}^{wtb}$ with integer constants, an equivalent TPN can be built with integer bounds but with a size exponential w.r.t. the original model. Surprisingly, using rational bounds yields a TPN whose size is linear.Subjects / Keywords
Time Petri Nets; Timed Automata; Weak Timed BisimilarityRelated items
Showing items related by title and author.
-
Roux, Olivier-Henri; Bérard, Béatrice; Cassez, Franck; Haddad, Serge; Lime, Didier (2005) Communication / Conférence
-
Roux, Olivier-Henri; Lime, Didier; Haddad, Serge; Cassez, Franck; Bérard, Béatrice (2005) Communication / Conférence
-
Bouyer, Patricia; Haddad, Serge; Reynier, Pierre-Alain (2006) Communication / Conférence
-
Bouyer, Patricia; Haddad, Serge; Reynier, Pierre-Alain (2006) Communication / Conférence
-
Bouyer, Patricia; Haddad, Serge; Reynier, Pierre-Alain (2008) Article accepté pour publication ou publié