A game approach to determinize timed automataReportar como inadecuado

A game approach to determinize timed automata - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 SUMO - SUpervision of large MOdular and distributed systems Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL 2 ISIMS - Institut Supérieur d-Informatique et de Multimédia de Sfax

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 343: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.

Autor: Nathalie Bertrand - Amélie Stainer - Thierry Jéron - Moez Krichen -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados