CTL is the dominant temporal specification language in practice mainly due to the fact that it admits model checking in linear time. Logic programming and the database query language Datalog are often used as an implementation platform for logic languages. In this paper we present the exact relation between CTL and Datalog and moreover we build on this relation and known efficient algorithms for CTL to obtain efficient algorithms for fragments of stratified Datalog. The contributions of this paper are: a) We embed CTL into STD which is a proper fragment of stratified Datalog. Moreover we show that STD expresses exactly CTL -- we prove that by embedding STD into CTL. Both embeddings are linear. b) CTL can also be embedded to fragments of Datalog without negation. We define a fragment of Datalog with the successor build-in predicate that we call TDS and we embed CTL into TDS in linear time. We build on the above relations to answer open problems of stratified Datalog. We prove that query evaluation is linear and that containment and satisfiability problems are both decidable. The results presented in this paper are the first for fragments of stratified Datalog that are more general than those containing only unary EDBs.
Model checking is closely related to database query evaluation. The idea is based on the principle that Kripke structures can be viewed as relational databases @cite_20 . One effective approach for efficiently implementing model checking is based on the translation of temporal formulae into automata and has become an intensive research area @cite_15 @cite_33 @cite_36 . Another approach consists in translating temporal logics to Logic Programming @cite_16 . Logic Programming has been successfully used as an implementation platform for verification systems such as model checkers. Translations of temporal logics such as CTL or @math -calculus into logic programming can be found in @cite_6 @cite_7 @cite_45 . @cite_7 presents the LMC project which uses XSB, a tabled logic programming system that extends Prolog-style SLD resolution with tabled resolution.
@cite_33 @cite_7 @cite_36 @cite_6 @cite_45 @cite_15 @cite_16 @cite_20
1498432697 2075969214 2081955678 2167672803
Our growing dependence on increasingly complex computer and software systems necessitates the development of formalisms, techniques, and tools for assessing functional properties of these systems. One such technique that has emerged in the last twenty years is model checking, which systematically (and automatically) checks whether a model of a given system satisfies a desired property such as deadlock freedom, invariants, and request-response properties. This automated technique for verification and debugging has developed into a mature and widely used approach with many applications. Principles of Model Checking offers a comprehensive introduction to model checking that is not only a text suitable for classroom use but also a valuable reference for researchers and practitioners in the field. The book begins with the basic principles for modeling concurrent and communicating systems, introduces different classes of properties (including safety and liveness), presents the notion of fairness, and provides automata-based algorithms for these properties. It introduces the temporal logics LTL and CTL, compares them, and covers algorithms for verifying these logics, discussing real-time systems as well as systems subject to random phenomena. Separate chapters treat such efficiency-improving techniques as abstraction and symbolic manipulation. The book includes an extensive set of examples (most of which run through several chapters) and a complete set of basic results accompanied by detailed proofs. Each chapter concludes with a summary, bibliographic notes, and an extensive list of exercises of both practical and theoretical nature. While model checking of pushdown systems is by now an established technique in software verification, temporal logics and automata traditionally used in this area are unattractive on two counts. First, logics and automata traditionally used in model checking cannot express requirements such as pre post-conditions that are basic to analysis of software. Second, unlike in the finite-state world, where the μ-calculus has a symbolic model-checking algorithm and serves as an “assembly language” to which temporal logics can be compiled, there is no common formalism—either fixpoint-based or automata-theoretic—to model-check requirements on pushdown models. In this article, we introduce a new theory of temporal logics and automata that addresses the above issues, and provides a unified foundation for the verification of pushdown systems. The key idea here is to view a program as a generator of structures known as nested trees as opposed to trees. A fixpoint logic (called N T -μ) and a class of automata (called nested tree automata) interpreted on languages of these structures are now defined, and branching-time model-checking is phrased as language inclusion and membership problems for these languages. We show that N T -μ and nested tree automata allow the specification of a new frontier of requirements usable in software verification. At the same time, their model checking problem has the same worst-case complexity as their traditional analogs, and can be solved symbolically using a fixpoint computation that generalizes, and includes as a special case, “summary”-based computations traditionally used in interprocedural program analysis. We also show that our logics and automata define a robust class of languages—in particular, just as the μ-calculus is equivalent to alternating parity automata on trees, NT-μ is equivalent to alternating parity automata on nested trees. As model checking becomes increasingly used in industry, there is a big need for efficient new methods to deal with the large real-size designs. The author presents a novel method for improving the performance of model checking using parallelisation techniques. The model checking is performed on a distributed-memory environment consisting of a network of machines. The important two keys to focus on are the memory balance and communication reduction. A new algorithm for partitioning the large state space modelling industrial designs with hundreds of millions of states and transitions is proposed. The state space is supposed to be represented by a weighted Kripke structure (this is an extension of the Kripke structure where weights are associated with the states and with the transitions). This algorithm partitions the weighted Kripke structure by performing a combination of abstraction-partition-refinement on this structure. The CTL model checking algorithm is distributed on processes located on different network machines. Each one owns a partition and executes the algorithm on it. The algorithm for CTL model checking is designed to reduce the communication overhead between the processes. The experimental results on large real designs show that this method improves the quality of partitions, the communication overhead and then the overall performance of the model checking. We study the problem of model checking software product line (SPL) behaviours against temporal properties. This is more difficult than for single systems because an SPL with n features yields up to 2n individual systems to verify. As each individual verification suffers from state explosion, it is crucial to propose efficient formalisms and heuristics. We recently proposed featured transition systems (FTS), a compact representation for SPL behaviour, and defined algorithms for model checking FTS against linear temporal properties. Although they showed to outperform individual system verifications, they still face a state explosion problem as they enumerate and visit system states one by one. In this paper, we tackle this latter problem by using symbolic representations of the state space. This lead us to consider computation tree logic (CTL) which is supported by the industry-strength symbolic model checker NuSMV. We first lay the foundations for symbolic SPL model checking by defining a feature-oriented version of CTL and its dedicated algorithms. We then describe an implementation that adapts the NuSMV language and tool infrastructure. Finally, we propose theoretical and empirical evaluations of our results. The benchmarks show that for certain properties, our algorithm is over a hundred times faster than model checking each system with the standard algorithm.