Games for the μ-calculus

Given a formula of the propositional μ-calculus, we construct a tableau of the formula and define an infinite game of two players of which one wants to show that the formula is satisfiable, and the other seeks the opposite. The strategy for the first player can be further transformed into a model of the formula while the strategy for the second forms what we call a refutation of the formula. Using Martin's Determinacy Theorem, we prove that any formula has either a model or a refutation. This completeness result is a starting point for the completeness theorem for the μ-calculus to be presented elsewhere. However, we argue that refutations have some advantages of their own. They are generated by a natural system of sound logical rules and can be presented as regular trees of the size exponential in the size of a refuted formula. This last aspect completes the small model theorem for the μ-calculus established by Emerson and Jutla (1988). Thus, on a more practical side, refutations can be used as small objects testifying incorrectness of a program specification expressed by a μ-formula, we illustrate this point by an example.

Authors

• Damian Niwiński
• Igor Walukiewicz

Keywords

No keywords are indexed for this paper.