uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Sampled universality of timed automata
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
2007 (English)In: Foundations of Software Science and Computational Structures, Proceedings / [ed] Seidl, H, 2007, 2-16 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2007. 2-16 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 4423
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-21147DOI: 10.1007/978-3-540-71389-0_2ISI: 000246296000002ISBN: 978-3-540-71388-3 (print)OAI: oai:DiVA.org:uu-21147DiVA: diva2:48920
Conference
10th International Conference on Fundamental Approaches to Software Engineering Braga, PORTUGAL, MAR 24-APR 01, 2007
Available from: 2007-05-21 Created: 2007-05-21 Last updated: 2011-04-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Abdulla, Parosh AzizKrcal, PavelYi, Wang

Search in DiVA

By author/editor
Abdulla, Parosh AzizKrcal, PavelYi, Wang
By organisation
Computer Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 452 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf