IEEE Transactions on Software Engineering · 2003 · 67 citations · 16 references
ComputingComputer ScienceDesign AutomationFormal MethodsLogicModel CheckingQuery ProcessingTemporal LogicCruise ControlCruise Control SystemsKripke StructuresModel Space ExplorationTemporal Logic ReasoningTest Case Generation
Temporal logic query checking was first introduced by W. Chan in order to speed up design understanding by discovering properties not known a priori. A query is a temporal logic formula containing a special symbol ?/sub 1/, known as a placeholder. Given a Kripke structure and a propositional formula /spl phi/, we say that /spl phi/ satisfies the query if replacing the placeholder by /spl phi/ results in a temporal logic formula satisfied by the Kripke structure. A solution to a temporal logic query on a Kripke structure is the set of all propositional formulas that satisfy the query. Query checking helps discover temporal properties of a system and, as such, is a useful tool for model exploration. In this paper, we show that query checking is applicable to a variety of model exploration tasks, ranging from invariant computation to test case generation. We illustrate these using a Cruise Control System. Additionally, we show that query checking is an instance of a multi-valued model checking of Chechik et al. This approach enables us to build an implementation of a temporal logic query checker, TLQSolver, on top of our existing multi-valued model checker /sub /spl chi//Chek. It also allows us to decide a large class of queries and introduce witnesses for temporal logic queries-an essential notion for effective model exploration.
16
E. M. Clarke, Orna Grümberg, D. Long · 1996 · 6.9K citations
Introduction to lattices and order
Choice Reviews Online · 1991 · 1.1K citations