From linear time to branching time
Authors:
Open Access
- 1 April 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 6 (2) , 273-294
Abstract
Model checking is a method for the verification of systems with respect to their specifications. Symbolic model-checking, which enables the verification of large systems, proceeds by calculating fixed-point expressions over the system's set of states. The μ-calculus is a branching-time temporal logic with fixed-point operators. As such, it is a convenient logic for symbolic model-checking tools. In particular, the alternation-free fragment of μ-calculus has a restricted syntax, making the symbolic evaluation of its formulas computationally easy. Formally, it takes time that is linear in the size of the system. On the other hand, specifiers find the μ-calculus inconvenient. In addition, specifiers often prefer to use linear-time formalisms. Such formalisms, however, cannot in general be translated to the alternation-free μ-calculus, and their symbolic evaluation involves nesting of fixed-points, resulting in time complexity that is quadratic in the size of the system. In this article, we characterize linear-time properties that can be specified in the alternation-free μ-calculus. We show that a linear-time property can be specified in the alternation-free μ-calculus iff it can be recognized by a deterministic Büchi automaton. We study the problem of deciding whether a linear-time property, specified by either an automaton or an LTL formula, can be translated to an alternation-free μ-calculus formula, and describe the translation, when possible.Keywords
This publication has 26 references indexed in Scilit:
- A New Heuristic for Bad Cycle Detection Using BDDsFormal Methods in System Design, 2001
- The model checker SPINIEEE Transactions on Software Engineering, 1997
- Buy one, get one free!!!Journal of Logic and Computation, 1996
- Symbolic model checking: 1020 States and beyondInformation and Computation, 1992
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- Automatic verification of finite-state concurrent systems using temporal logic specificationsACM Transactions on Programming Languages and Systems, 1986
- “Sometimes” and “not never” revisitedJournal of the ACM, 1986
- Results on the propositional μ-calculusTheoretical Computer Science, 1983
- AlternationJournal of the ACM, 1981
- Space-bounded reducibility among combinatorial problemsJournal of Computer and System Sciences, 1975