When are timed automata weakly timed bisimilar to time petri nets?

Beatrice Bérard*, Franck Cassez, Serge Haddad, Didier Lime, Olivier H. Roux

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

11 Citations (Scopus)

Abstract

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 T Awtb 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 T Awtb are PSPACE-complete. Furthermore we show that for a TA in T Awtb 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.

Original languageEnglish
Title of host publicationFSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science - 25th International Conference, Proceedings
Place of PublicationNew York
PublisherSpringer, Springer Nature
Pages273-284
Number of pages12
Volume3821 LNCS
ISBN (Print)3540304959, 9783540304951
Publication statusPublished - 2005
Externally publishedYes
Event25th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2005 - Hyderabad, India
Duration: 15 Dec 200518 Dec 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3821 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other25th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2005
CountryIndia
CityHyderabad
Period15/12/0518/12/05

Keywords

  • Time Petri Nets
  • Timed Automata
  • Weak Timed Bisimilarity

Fingerprint Dive into the research topics of 'When are timed automata weakly timed bisimilar to time petri nets?'. Together they form a unique fingerprint.

  • Cite this

    Bérard, B., Cassez, F., Haddad, S., Lime, D., & Roux, O. H. (2005). When are timed automata weakly timed bisimilar to time petri nets? In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science - 25th International Conference, Proceedings (Vol. 3821 LNCS, pp. 273-284). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3821 LNCS). New York: Springer, Springer Nature.