A Characterisation of Pi^0_2 Regular Tree Languages
Filippo Cavallari, Henryk Michalewski, Michał Skrzypczak · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2017
We show an algorithm that for a given regular tree language L decides if L is in Pi^0_2, that is if L belongs to the second level of Borel Hierarchy. Moreover, if L is in Pi^0_2, then we construct a weak alternating automaton of index (0, 2) which recognises L. We also prove that for a given language L, L is recognisable by a weak alternating (1, 3)-automaton if and only if it is recognisable by a weak non-deterministic (1, 3)-automaton.