Improvements in SAT-based Reachability Analysis for Timed Automata

Issue title: Concurrency Specification and Programming (CS&P 2003)

Article type: Research Article

Authors: Zbrzezny, Andrzej

Affiliations: Institute of Mathematics and Computer Science, Pedagogical University of Czestochowa, Al. Armii Krajowej 13/15, 42-200 Czestochowa, Poland

Abstract: The paper deals with the problem of checking reachability for timed automata. In order to check reachability of a~state satisfying some property, first the transition relation of a timed automaton is unfolded iteratively to some depth and encoded as a propositional formula. Next, the property is translated to a propositional formula and satisfiability of the conjunction of the two defined above formulas is checked. The unfolding of the transition relation can be terminated when either a state satisfying the property has been found or all the states of the timed automaton have been searched. In this paper we propose some improvements of the encoding of the transition relation for timed automata. The improvements are partially based on a new discretization scheme. The efficiency of the improved encoding is strongly supported by the experimental results. We also introduce a method for checking unreachability.

Journal: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 417-434, 2004