Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

Download [help]

Download paper Adobe portable document format (pdf)

Copyright noticeThis material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

In this paper, we define two relaxed semantics (one based on probabilities and the other one based on the topological notion of largeness) for LTL over infinite runs of timed automata which rule out unlikely sequences of events. We prove that these two semantics match in the framework of single-clock timed automata (and only in that framework), and prove that the corresponding relaxed model-checking problems are PSPACE-Complete. Moreover, we prove that the probabilistic non-Zenoness can be decided for single-clock timed automata in NLOGSPACE.

Contact

Nathalie Bertrand
nathalie.bertrand@irisa.fr

BibTex Reference

@InProceedings{BBBBG-lics08,
   Author = {Baier, Christel and Bertrand, Nathalie and Bouyer, Patricia and Brihaye, Thomas and Groesser, Marcus},
   Title = {Almost-Sure Model Checking of Infinite Paths in One-Clock Timed Automata},
   BookTitle = {{P}roceedings of the 23rd {A}nnual {IEEE} {S}ymposium on {L}ogic in {C}omputer {S}cience ({LICS}'08)},
   Publisher = {IEEE Computer Society Press},
   Address = {Pittsburgh, PA, USA},
   Month = {June},
   Year = {2008}
}

EndNote Reference [help]

Get EndNote Reference (.ref)