Loading [MathJax]/extensions/MathZoom.js
The alternation hierarchy for the theory of μ-lattices
Santocanale, Luigi
HAL, hal-01261116 / Harvested from HAL
The alternation hierarchy problem asks whether every μ-term φ, 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 μ-term where the number of nested fixed points of a different type is bounded by a constant independent of φ. In this paper we give a proof that the alternation hierarchy for the theory of μ-lattices is strict, meaning that such a constant does not exist if μ-terms are built up from the basic lattice operations and are interpreted as expected. The proof relies on the explicit characterization of free μ-lattices by means of games and strategies.
Publié le : 2002-07-04
Classification:  [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO],  [MATH.MATH-CT]Mathematics [math]/Category Theory [math.CT]
@article{hal-01261116,
     author = {Santocanale, Luigi},
     title = {The alternation hierarchy for the theory of $\mu$-lattices },
     journal = {HAL},
     volume = {2002},
     number = {0},
     year = {2002},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-01261116}
}
Santocanale, Luigi. The alternation hierarchy for the theory of μ-lattices . HAL, Tome 2002 (2002) no. 0, . http://gdmltest.u-ga.fr/item/hal-01261116/