Sökning: onr:"swepub:oai:DiVA.org:uu-21147" >
Sampled universalit...
Sampled universality of timed automata
-
- Abdulla, Parosh Aziz (författare)
- Uppsala universitet,Datorteknik
-
- Krcal, Pavel (författare)
- Uppsala universitet,Datorteknik
-
- Yi, Wang (författare)
- Uppsala universitet,Datorteknik,Embedded Systems
-
(creator_code:org_t)
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2007
- 2007
- Engelska.
-
Ingår i: Foundations of Software Science and Computational Structures, Proceedings. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783540713883 ; , s. 2-16
- Relaterad länk:
-
https://link.springe...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Timed automata can be studied in not only a dense-time setting but also a discrete-time setting. The most common example of discrete-time semantics is the so called sampled semantics (i.e., discrete semantics with a fixed time granularity epsilon). In the real-time setting, the universality problem is known to be undecidable for timed automata. In this work, we study the universality question for the languages accepted by timed automata with sampled semantics. On the negative side, we show that deciding whether for all sampling periods epsilon a timed automaton accepts all timed words in epsilon-sampled semantics is as hard as in the real-time case, i.e., undecidable. On the positive side, we show that checking whether there is a sampling period such that a timed automaton accepts all untimed words in epsilon-sampled semantics is decidable. Our proof uses clock difference relations, developed to characterize the reachability relation for timed automata in connection with sampled semantics.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Computer science
- Datavetenskap
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas