zbMATH — the first resource for mathematics

Robust analysis of timed automata via channel machines. (English) Zbl 1138.68431
Amadio, Roberto (ed.), Foundations of software science and computational structures. 11th international conference, FOSSACS 2008, held as part of the joint European conferences on theory and practice of software, ETAPS 2008, Budapest, Hungary, March 29–April 6, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78497-5/pbk). Lecture Notes in Computer Science 4962, 157-171 (2008).
Summary: Whereas formal verification of timed systems has become a very active field of research, the idealised mathematical semantics of timed automata cannot be faithfully implemented. Several works have thus focused on a modified semantics of timed automata which ensures implementability, and robust model-checking algorithms for safety, and later LTL properties have been designed. Recently, a new approach has been proposed, which reduces (standard) model-checking of timed automata to other verification problems on channel machines. Thanks to a new encoding of the modified semantics as a network of timed systems, we propose an original combination of both approaches, and prove that robust model-checking for coFlat-MTL, a large fragment of MTL, is EXPSPACE-Complete.
For the entire collection see [Zbl 1133.68001].

68Q45 Formal languages and automata
68Q60 Specification and verification (program logics, model checking, etc.)
Full Text: DOI