Simple On-the-fly Automatic Verification of Linear Temporal Logic

A tableau-based algorithm for obtaining an automaton from a temporal logic formula that can be constructed simultaneously with, and guided by, the generation of the model, and which can be used in model checking in an “on-the-fly” fashion.

Abstract

We present a tableau-based algorithm for obtaining an automaton from a temporal logic formula. The algorithm is geared towards being used in model checking in an "on-the-fly" fashion, that is the automaton can be constructed simultaneously with, and guided by, the generation of the model. In particular, it is possible to detect that a property does not hold by only constructing part of the model and of the automaton. The algorithm can also be used to check the validity of a temporal logic assertion. Although the general problem is PSPACE-complete, experiments show that our algorithm performs quite well on the temporal formulas typically encountered in verification. While basing linear-time temporal logic model-checking upon a transformation to automata is not new, the details of how to do this efficiently, and in "on-the-fly" fashion have never been given.