The power of reachability testing for timed automata

✍ Scribed by Luca Aceto; Patricia Bouyer; Augusto Burgueño; Kim G Larsen

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 824 KB
• Volume: 300
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00334-1

✦ Synopsis

The computational engine of the veriÿcation tool UPPAAL consists of a collection of e cient algorithms for the analysis of reachability properties of systems. Model-checking of properties other than plain reachability ones may currently be carried out in such a tool as follows. Given a property to model-check, the user must provide a test automaton T for it. This test automaton must be such that the original system S has the property expressed by precisely when none of the distinguished reject states of T can be reached in the synchronized parallel composition of S with T . This raises the question of which properties may be analysed by UPPAAL in such a way. This paper gives an answer to this question by providing a complete characterization of the class of properties for which model-checking can be reduced to reachability testing in the sense outlined above. This result is obtained as a corollary of a stronger statement pertaining to the compositionality of the property language considered in this study. In particular, it is shown