TY - JOUR AU - Santocanale, Luigi PY - 2000/01/29 Y2 - 2024/03/28 TI - The Alternation Hierarchy for the Theory of mu-lattices JF - BRICS Report Series JA - BRICS VL - 7 IS - 29 SE - Articles DO - 10.7146/brics.v7i29.20163 UR - https://tidsskrift.dk/brics/article/view/20163 SP - AB - The alternation hierarchy problem asks whether every mu-term,<br />that is a term built up using also a least fixed point constructor<br />as well as a greatest fixed point constructor, is equivalent to a<br />mu-term where the number of nested fixed point of a different type<br />is bounded by a fixed number.<br />In this paper we give a proof that the alternation hierarchy<br />for the theory of mu-lattices is strict, meaning that such number<br />does not exist if mu-terms are built up from the basic lattice <br />operations and are interpreted as expected. The proof relies on the<br />explicit characterization of free mu-lattices by means of games and<br />strategies. ER -