Lecture Notes in Computer Science, 2008, Volume 5156/2008, 95-113, DOI: 10.1007/978-3-540-85114-1_9

State Focusing: Lazy Abstraction for the Mu-Calculus

Harald Fecher and Sharon Shoham

View Related Documents

Abstract

A key technique for the verification of programs is counterexample-guided abstraction refinement (CEGAR). In a previous approach, we developed a CEGAR-based algorithm for the modal μ-calculus, where refinement applies only locally, i.e. lazy abstraction techniques are used. Unfortunately, our previous algorithm was not completely lazy and had some further drawbacks, like a possible local state explosion. In this paper, we present an improved algorithm that maintains all advantages of our previous algorithm but eliminates all its drawbacks. The improvements were only possible by changing the philosophy of refinement from state splitting into the new philosophy of state focusing, where the states that are about to be split are not removed.
This work is financially supported by the DFG projects (FE 942/2-1) and (SFB/TR 14 AVACS).

Fulltext Preview

Image of the first page of the fulltext document