• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
timed_automata.PDF (523.3Kb)
Type
Communication / Conférence
Date
2005
Conference title
FSTTCS 2005 25th International Conference on Foundations of Software Technology and Theoretical Computer Science
Conference date
2005-12
Conference city
Hyderabad
Conference country
Inde
Book title
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings
Book author
Sen, Sandeep; Ramanujam, R.
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
3821
Published in
Berlin
ISBN
978-3-540-30495-1
Number of pages
566
Pages
273-284
Publication identifier
http://dx.doi.org/10.1007/11590156_22
Metadata
Show full item record
Author(s)
Roux, Olivier-Henri
Lime, Didier
Haddad, Serge
Cassez, Franck
Bérard, Béatrice
Abstract (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 Bisimilarity

Related items

Showing items related by title and author.

  • Thumbnail
    Comparison of the Expressiveness of Timed Automata and Time Petri Nets 
    Roux, Olivier-Henri; Bérard, Béatrice; Cassez, Franck; Haddad, Serge; Lime, Didier (2005) Communication / Conférence
  • Thumbnail
    Comparison of Different Semantics for Time Petri Nets 
    Roux, Olivier-Henri; Lime, Didier; Haddad, Serge; Cassez, Franck; Bérard, Béatrice (2005) Communication / Conférence
  • Thumbnail
    Extended Timed Automata and Time Petri Nets 
    Bouyer, Patricia; Haddad, Serge; Reynier, Pierre-Alain (2006) Communication / Conférence
  • Thumbnail
    Timed Petri Nets and Timed Automata: On the Discriminating Power of Zeno Sequences 
    Bouyer, Patricia; Haddad, Serge; Reynier, Pierre-Alain (2006) Communication / Conférence
  • Thumbnail
    Timed Petri nets and timed automata: On the discriminating power of zeno sequences 
    Bouyer, Patricia; Haddad, Serge; Reynier, Pierre-Alain (2008) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo