In: R. Ramanujam, Sandeep Sen (Eds.): Lecture Notes in Computer Science, 3821: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science: 25th International Conference, Hyderabad, India, December 15-18, 2005., pages 273-284. Springer-Verlag, December 2005. URL: http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1007/1159015622,.
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 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 TA{wtb are PSPACE-complete. Furthermore we show that for a TA in 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.
Keywords: Time Petri Nets, Timed Automata, Weak Timed Bisimilarity..