@article{ArnoldSantocanale:TCS:2005,
    Abstract = {A classical result by Rabin states that if a set of trees and its complement are both B{\"u}chi definable in the monadic second order logic, then these sets are weakly definable. In the language of {$\mu$}-calculi, this theorem asserts the equality between the complexity classes Σ2∩Π2 and Comp(Σ1,Π1) of the fixed-point alternation-depth hierarchy of the {$\mu$}-calculus of tree languages. It is natural to ask whether at higher levels of the hierarchy the ambiguous classes Σn+1∩Πn+1 and the composition classes Comp(Σn,Πn) are equal, and for which {$\mu$}-calculi. The first result of this paper is that the alternation-depth hierarchy of the games {$\mu$}-calculus---whose canonical interpretation is the class of all complete lattices---enjoys this property. More explicitly, every parity game which is equivalent both to a game in Σn+1 and to a game in Πn+1 is also equivalent to a game obtained by composing games in Σn and Πn. The second result is that the alternation-depth hierarchy of the {$\mu$}-calculus of tree languages does not enjoy the property. Taking into account that any B{\"u}chi definable set is recognized by a nondeterministic B{\"u}chi automaton, we generalize Rabin's result in terms of the following separation theorem: if two disjoint languages are recognized by nondeterministic Πn+1 automata, then there exists a third language recognized by an alternating automaton in Comp(Σn,Πn) containing one and disjoint from the other. Finally, we lift the results obtained for the {$\mu$}-calculus of tree languages to the propositional modal {$\mu$}-calculus: ambiguous classes do not coincide with composition classes, but a separation theorem is established for disjunctive formulas.},
    Author = {Santocanale, Luigi and Arnold, Andr{\'e}},
    File = {Ambiguous classes in µ-calculi hierarchies - 1-s2.0-S0304397504007145-main - a - y.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Note = {Foundations of Software Science and Computation Structures},
    Number = {1},
    Pages = {265--296},
    Title = {Ambiguous classes in {$\mu$}-calculi hierarchies},
    URL = {http://www.sciencedirect.com/science/article/pii/S0304397504007145},
    Volume = {333},
    Year = {2005},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397504007145},
    bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2004.10.024},
    date-added = {2020-08-05 11:02:55 +0200},
    date-modified = {2020-08-05 11:03:14 +0200},
    doi = {10.1016/j.tcs.2004.10.024}
}

@article{ArnoldSantocanale:TCS:2005, Abstract = {A classical result by Rabin states that if a set of trees and its complement are both B{\"u}chi definable in the monadic second order logic, then these sets are weakly definable. In the language of {$\mu$}-calculi, this theorem asserts the equality between the complexity classes Σ2∩Π2 and Comp(Σ1,Π1) of the fixed-point alternation-depth hierarchy of the {$\mu$}-calculus of tree languages. It is natural to ask whether at higher levels of the hierarchy the ambiguous classes Σn+1∩Πn+1 and the composition classes Comp(Σn,Πn) are equal, and for which {$\mu$}-calculi. The first result of this paper is that the alternation-depth hierarchy of the games {$\mu$}-calculus---whose canonical interpretation is the class of all complete lattices---enjoys this property. More explicitly, every parity game which is equivalent both to a game in Σn+1 and to a game in Πn+1 is also equivalent to a game obtained by composing games in Σn and Πn. The second result is that the alternation-depth hierarchy of the {$\mu$}-calculus of tree languages does not enjoy the property. Taking into account that any B{\"u}chi definable set is recognized by a nondeterministic B{\"u}chi automaton, we generalize Rabin's result in terms of the following separation theorem: if two disjoint languages are recognized by nondeterministic Πn+1 automata, then there exists a third language recognized by an alternating automaton in Comp(Σn,Πn) containing one and disjoint from the other. Finally, we lift the results obtained for the {$\mu$}-calculus of tree languages to the propositional modal {$\mu$}-calculus: ambiguous classes do not coincide with composition classes, but a separation theorem is established for disjunctive formulas.}, Author = {Santocanale, Luigi and Arnold, Andr{\'e}}, File = {Ambiguous classes in µ-calculi hierarchies - 1-s2.0-S0304397504007145-main - a - y.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Note = {Foundations of Software Science and Computation Structures}, Number = {1}, Pages = {265--296}, Title = {Ambiguous classes in {$\mu$}-calculi hierarchies}, URL = {http://www.sciencedirect.com/science/article/pii/S0304397504007145}, Volume = {333}, Year = {2005}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397504007145}, bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2004.10.024}, date-added = {2020-08-05 11:02:55 +0200}, date-modified = {2020-08-05 11:03:14 +0200}, doi = {10.1016/j.tcs.2004.10.024} }