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

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.
Type de document :
Communication dans un congrès
23rd Annual IEEE Symposium on Logic in Computer Science (LICS'08), Jun 2008, Pittsburgh, United States. IEEE, pp.217-226, 2008, 〈10.1109/LICS.2008.25〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00424520
Contributeur : Nathalie Bertrand <>
Soumis le : vendredi 16 octobre 2009 - 11:07:51
Dernière modification le : mercredi 11 avril 2018 - 01:52:32

Lien texte intégral

Identifiants

Collections

Citation

Christel Baier, Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Marcus Größer. Almost-Sure Model Checking of Infinite Paths in One-Clock Timed Automata.. 23rd Annual IEEE Symposium on Logic in Computer Science (LICS'08), Jun 2008, Pittsburgh, United States. IEEE, pp.217-226, 2008, 〈10.1109/LICS.2008.25〉. 〈inria-00424520〉

Partager

Métriques

Consultations de la notice

131