A game approach to determinize timed automata

Abstract : Timed automata are frequently used to model real-time systems. Their determinization is a key issue for several validation problems. However, not all timed automata can be determinized, and determinizability itself is undecidable. In this paper, we propose a game-based algorithm which, given a timed automaton, tries to produce a language-equivalent deterministic timed automaton, otherwise a deterministic over-approximation. Our method generalizes two recent contributions: the determinization procedure of Baier et al. (Proceedings of the 36th international colloquium on automata, languages and programming (ICALP'09), 2009) and the approximation algorithm of Krichen and Tripakis (Form Methods Syst Des 34(3):238–304, 2009). Moreover, we extend it to apply to timed automata with invariants and ε-transitions, and also consider other useful approximations: under-approximation, and combination of under- and over-approximations.
Type de document :
Article dans une revue
Formal Methods in System Design, Springer Verlag, 2015, pp.39. 〈10.1007/s10703-014-0220-1〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01102472
Contributeur : Nathalie Bertrand <>
Soumis le : lundi 12 janvier 2015 - 18:01:02
Dernière modification le : mercredi 16 mai 2018 - 11:24:07
Document(s) archivé(s) le : lundi 13 avril 2015 - 11:15:35

Fichier

BSJK-fmsd14.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Nathalie Bertrand, Amélie Stainer, Thierry Jéron, Moez Krichen. A game approach to determinize timed automata. Formal Methods in System Design, Springer Verlag, 2015, pp.39. 〈10.1007/s10703-014-0220-1〉. 〈hal-01102472〉

Partager

Métriques

Consultations de la notice

420

Téléchargements de fichiers

124