Deciding the weak definability of B?chi definable tree languages

摘要

Weakly definable languages of infinite trees are an expressive subclass of regular tree languages definable in terms of weak monadic second-order logic, or equivalently weak alternating automata. Our main result is that given a B?chi automaton, it is deci