Real-time systems are reactive systems whose behavior depends on the timing of the actions performed by the systems. Many real-time systems can be represented by timed automata, which are finite-state automata extended with variables representing clocks. Systems represented by timed automata are infinite-state because their clock variables range over an infinite domain.
Model checking is a verification technique aimed at determining whether a system specification possesses a property expressed as a temporal logic formula. Model checking is traditionally used to verify finite-state systems. It can also be applied to systems represented by timed automata through the use of region graphs. The region graph of a timed automaton represents a finite partition of the infinite state space underlying the timed automaton.
In my thesis, I present a flexible framework for the verification of finite-state systems as well as infinite-state systems. The framework is based on logic programming and constraints. The semantics of the system specification language and the temporal logic are encoded as rules of logic programs. Constraints are used to represent possibly infinite sets of states. To perform the fixed point computations required during model checking, I also use tabling, a logic programming technique for memorizing predicate invocations and answers.
I implemented the framework by integrating the tabled logic programming system XSB (from SUNYSB) and the constraint package POLINE (from VERIMAG). I developed an algorithm for the verification of real-time systems represented by timed automata. The algorithm is based on region graphs, and is capable of computing answers for reachability questions as well as formulas written in the modal mu-calculus, a very expressive temporal logic. It is also a local algorithm, which means that it explores only the part of the state space relevant to the satisfaction of the formula to be verified. The algorithm is implemented in the tool XMC/RT, and experiments show that its performance is comparable to that of HyTech.
In timed automata, there are restrictions on how the clock variables can be updated. In my thesis, I extend the region-graph-based technique to a richer class of infinite-state systems, one that includes timed automata but also untimed systems in which variables can be updated in more general ways. These systems include various kinds of control algorithms, such as mutual exclusion algorithms that involve unbounded integer variables. In particular, I identified a class of infinite-state systems called Strongly Partition Preserving Automata (SPPA), for which the modal mu-calculus model-checking problem is decidable using region graphs. SPPA is a kind of guarded-command automata whose transitions ``preserve'' the partitions of its region graph. The well-known bakery algorithm, a problem that has been widely used to illustrate deductive techniques and semi-decision procedures for verifying infinite-state systems, is in SPPA and hence decidable using region graphs. These results can be seen as bridging the gap between research on automatic techniques for verifying real-time systems and the broad body of work on decision procedures for (untimed) infinite-state systems.
My thesis shows that region-graph-based techniques can be effectively used for model checking both real-time and untimed infinite-state systems. These techniques can be naturally encoded in the framework of tabled logic programming with constraints. This encoding allows other techniques developed for logic-based model checking, such as induction proofs based on program transformation, to be extended to real-time and untimed infinite-state systems.
Xiaoqun Du 2001-11-11