Definable Operations On Weakly Recognizable Sets of Trees

Jacques Duparc, Alessandro Facchini & Filip Murlak
Alternating automata on infinite trees induce operations on languages which do not preserve natural equivalence relations, like having the same Mostowski--Rabin index, the same Borel rank, or being continuously reducible to each other (Wadge equivalence). In order to prevent this, alternation needs to be restricted to the choice of direction in the tree. For weak alternating automata with restricted alternation a small set of computable operations generates all definable operations, which implies that the Wadge...