Weak index versus Borel rank
Filip Murlak · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2008
We investigate weak recognizability of deterministic languages of infinite trees. We prove that for deterministic languages the Borel hierarchy and the weak index hierarchy coincide. Furthermore, we propose a procedure computing for a deterministic automaton an equivalent minimal index weak automaton with a quadratic number of states. The algorithm works within the time of solving the emptiness problem.