Freedom, Weakness, and Determinism: From Linear-time to Branching-time

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 modelchecking tools. In particular, the alternationfree 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 paper we cha..