Almost-Sure Model Checking of Infinite Paths in One-Clock Timed Automata

Christel BaierChristel Baier, Nathalie BertrandNathalie Bertrand, Patricia BouyerPatricia Bouyer, Thomas BrihayeThomas Brihaye, Marcus GrößerMarcus Größer

DOI Link

Christel Baier, Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Marcus Größer
Almost-Sure Model Checking of Infinite Paths in One-Clock Timed Automata
Proc. of the 23rd IEEE Symposium on Logic in Computer Science (LICS), 217--226, 2008. IEEE Computer Society Press

Details
Bibtex

KurzfassungAbstract
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-clocktimed automata in NLOGSPACE.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{BBBBG2008,
  author    = {Christel Baier and Nathalie Bertrand and Patricia Bouyer and
               Thomas Brihaye and Marcus Gr{\"{o}}{\ss}er},
  title     = {Almost-Sure Model Checking of Infinite Paths in One-Clock Timed
               Automata},
  booktitle = {Proc. of the 23rd {IEEE} Symposium on Logic in Computer Science
               (LICS)},
  publisher = {IEEE Computer Society Press},
  year      = {2008},
  pages     = {217--226},
  doi       = {10.1109/LICS.2008.25}
}