Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-10T04:21:48.324Z Has data issue: false hasContentIssue false

Mu-depth 3 is more than 2: a game-theoretic proof

Published online by Cambridge University Press:  30 March 2001

GIACOMO LENZI
Affiliation:
LaBRI, Université Bordeaux I, 351, Cours de la Libération, F-33405 Talence cedex, France. Email: lenzi@labri.u-bordeaux.fr Dip. Mat. Appl. ‘U.Dini’, Università di Pisa, Via Bonanno 25B, 56100 Pisa, Italia.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider the propositional modal mu-calculus, a logic proposed by Kozen in 1983. In this logic two operators μ and v are present, which express the least and greatest fixpoints of monotone operators on sets. Bradfield in 1998 proved for any n the existence of a mu-calculus formula that requires n alternations of μ and v. In this paper we consider the particular case n = 3 and we exhibit a new formula requiring 3 alternations. Our proof is independent of the technique of Bradfield, and is based on a new kind of game on infinite trees.

Information

Type
Research Article
Copyright
2001 Cambridge University Press