Checking Timed Buechi Automata Emptiness Efficiently

摘要

This paper presents an on-the-fly and symbolic technique for efficiently checking timed automata emptiness. It is symbolic because it uses the simulation graph (instead of the region graph). It is on-the-fly because the simulation graph is generated during the test for emptiness. We have implemented a verification tool called Profounder based on this technique. To our knowledge, Profounder is the only available tool for checking emptiness of timed Biichi automata. To illustrate the practical interest of our approach, we show the performances of the tool on a non-trivial case study.