Show simple item record

dc.contributor.authorRoux, Olivier-Henri
HAL ID: 17486
dc.contributor.authorLime, Didier
HAL ID: 17326
dc.contributor.authorHaddad, Serge
HAL ID: 745039
dc.contributor.authorCassez, Franck
dc.contributor.authorBérard, Béatrice
HAL ID: 9360
dc.date.accessioned2011-01-28T11:07:45Z
dc.date.available2011-01-28T11:07:45Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5576
dc.language.isoenen
dc.subjectTime Petri Netsen
dc.subjectTimed Automataen
dc.subjectWeak Timed Bisimilarityen
dc.subject.ddc004en
dc.titleWhen are Timed Automata Weakly Timed Bisimilar to Time Petri Nets?en
dc.typeCommunication / Conférence
dc.description.abstractenIn 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.en
dc.identifier.citationpages273-284en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber3821
dc.relation.ispartoftitleFSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedingsen
dc.relation.ispartofeditorSen, Sandeep
dc.relation.ispartofeditorRamanujam, R.
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2005
dc.relation.ispartofpages566en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/11590156en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelInformatique généraleen
dc.relation.ispartofisbn978-3-540-30495-1en
dc.relation.conftitleFSTTCS 2005 25th International Conference on Foundations of Software Technology and Theoretical Computer Scienceen
dc.relation.confdate2005-12
dc.relation.confcityHyderabaden
dc.relation.confcountryIndeen
dc.identifier.doihttp://dx.doi.org/10.1007/11590156_22


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record