zbMATH — the first resource for mathematics

Symbolic robustness analysis of timed automata. (English) Zbl 1141.68429
Asarin, Eugene (ed.) et al., Formal modeling and analysis of timed systems. 4th international conference, FORMATS 2006, Paris, France, September 25–27, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-45026-9/pbk). Lecture Notes in Computer Science 4202, 143-155 (2006).
Summary: We propose a symbolic algorithm for the analysis of the robustness of timed automata, that is the correctness of the model in presence of small drifts on the clocks or imprecision in testing guards. This problem is known to be decidable with an algorithm based on detecting strongly connected components on the region graph, which, for complexity reasons, is not effective in practice.
Our symbolic algorithm is based on the standard algorithm for symbolic reachability analysis using zones to represent symbolic states and can then be easily integrated within tools for the verification of timed automata models. It relies on the computation of the stable zone of each cycle in a timed automaton. The stable zone is the largest set of states that can reach and be reached from itself through the cycle. To compute the robust reachable set, each stable zone that intersects the set of explored states has to be added to the set of states to be explored.
For the entire collection see [Zbl 1137.68001].

68Q45 Formal languages and automata
PDF BibTeX Cite
Full Text: DOI