Skip to Main content Skip to Navigation
Conference papers

Comparison of the Expressiveness of Timed Automata and Time Petri Nets

Abstract : In this paper we consider the model of Time Petri Nets (TPN) where time is associated with transitions. We also consider Timed Automata (TA) as defined by Alur \& Dill, and compare the expressive- ness of the two models w.r.t. timed language acceptance and (weak) timed bisimilarity. We first prove that there exists a TA A s.t. there is no TPN (even unbounded) that is (weakly) timed bisimilar to A. We then propose a structural translation from TA to (1-safe) TPNs preserv- ing timed language acceptance. Further on, we prove that the previous (slightly extended) translation also preserves weak timed bisimilarity for a syntactical subclass $T_{Asyn}(\leq,\geq)$ of TA. For the theory of TPNs, the consequences are: 1) TA, bounded TPNs and 1-safe TPNs are equally expressive w.r.t. timed language acceptance; 2) TA are strictly more expressive than bounded TPNs w.r.t. timed bisimilarity; 3) The subclass $T_{Asyn}(\leq,\geq)$, bounded and 1-safe TPNs ''`a la Merlin'' are equally ex- pressive w.r.t. timed bisimilarity.
Document type :
Conference papers
Complete list of metadata
Contributor : Franck Cassez Connect in order to contact the contributor
Submitted on : Tuesday, March 17, 2009 - 4:53:30 AM
Last modification on : Wednesday, April 27, 2022 - 3:49:17 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:36:00 PM



Béatrice Berard, Franck Cassez, Serge Haddad, Didier Lime, Olivier Henri Roux. Comparison of the Expressiveness of Timed Automata and Time Petri Nets. FORMATS 2005 - 3rd International Conference on Formal Modeling and Analysis of Timed Systems, Sep 2005, Uppsala, Sweden. pp.211-225, ⟨10.1007/11603009_17⟩. ⟨inria-00368577⟩



Record views


Files downloads