Show simple item record

Interrupt Timed Automata

dc.contributor.authorBérard, Béatrice
HAL ID: 9360
dc.contributor.authorHaddad, Serge
HAL ID: 745039
dc.date.accessioned2010-11-16T11:22:17Z
dc.date.available2010-11-16T11:22:17Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5082
dc.language.isoenen
dc.subjecthybrid automataen
dc.subjecttimed automataen
dc.subjectmulti-task systemsen
dc.subjectinterruptionsen
dc.subjectdecidability of reachabilityen
dc.subject.ddc004en
dc.titleInterrupt Timed Automataen
dc.typeCommunication / Conférence
dc.description.abstractenIn this work, we introduce the class of Interrupt Timed Automata (ITA), which are well suited to the description of multi-task systems with interruptions in a single processor environment. This model is a subclass of hybrid automata. While reachability is undecidable for hybrid automata we show that in ITA the reachability problem is in 2- EXPSPACE and in PSPACE when the number of clocks is fixed, with a procedure based on a generalized class graph. Furthermore we consider a subclass ITA− which still describes usual interrupt systems and for which the reachability problem is in NEXPTIME and in NP when the number of clocks is fixed (without any class graph). There exist languages accepted by an ITA− but neither by timed automata nor by controlled real-time automata (CRTA), another extension of timed automata. However we conjecture that CRTA is not contained in ITA. So, we combine ITA with CRTA in a model which encompasses both classes and show that the reachability problem is still decidable.en
dc.identifier.citationpages197-211en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber5504
dc.relation.ispartoftitleFoundations of Software Science and Computational Structures 12th International Conference, FOSSACS 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22-29, 2009. Proceedingsen
dc.relation.ispartofeditorde Alfaro, Luca
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2009
dc.relation.ispartofpages471en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-00596-1en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelInformatique généraleen
dc.relation.ispartofisbn978-3-642-00595-4en
dc.relation.conftitle12th International Conference on Foundations of Software Science and Computation Structures (FOSSACS 2009)en
dc.relation.confdate2009-03
dc.relation.confcityYorken
dc.relation.confcountryRoyaume-Unien
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-00596-1_15


Files in this item

Thumbnail
Name:
fossacs2009.pdf
Size:
189.8Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record