Geodesic
The alternation hierarchy for the theory of $\mu$-lattices
Theory and applications of categories, CT2000, Tome 9 (2001), pp. 166-197

Voir la notice de l'article provenant de la source Theory and Applications of Categories website

The alternation hierarchy problem asks whether every $\mu$-term $\phi$, that is, a term built up also using a least fixed point constructor as well as a greatest fixed point constructor, is equivalent to a $\mu$-term where the number of nested fixed points of a different type is bounded by a constant independent of $\phi$.

In this paper we give a proof that the alternation hierarchy for the theory of $\mu$-lattices is strict, meaning that such a constant does not exist if $\mu$-terms are built up from the basic lattice operations and are interpreted as expected. The proof relies on the explicit characterization of free $\mu$-lattices by means of games and strategies.

Classification : 03D55, 06B25, 91A43.
Keywords: free lattices, free �-lattices, fixed points, parity games. 
@article{TAC_2001_9_a8,
     author = {Luigi Santocanale},
     title = {The alternation hierarchy for the theory of $\mu$-lattices},
     journal = {Theory and applications of categories},
     pages = {166--197},
     publisher = {mathdoc},
     volume = {9},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TAC_2001_9_a8/}
}
TY  - JOUR
AU  - Luigi Santocanale
TI  - The alternation hierarchy for the theory of $\mu$-lattices
JO  - Theory and applications of categories
PY  - 2001
SP  - 166
EP  - 197
VL  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TAC_2001_9_a8/
LA  - en
ID  - TAC_2001_9_a8
ER  - 
%0 Journal Article
%A Luigi Santocanale
%T The alternation hierarchy for the theory of $\mu$-lattices
%J Theory and applications of categories
%D 2001
%P 166-197
%V 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TAC_2001_9_a8/
%G en
%F TAC_2001_9_a8
Luigi Santocanale. The alternation hierarchy for the theory of $\mu$-lattices. Theory and applications of categories, CT2000, Tome 9 (2001), pp. 166-197. http://geodesic.mathdoc.fr/item/TAC_2001_9_a8/