2026-07-23T16:08:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1318 2024-03-06T10:33:02Z ddc:004 open_access

Weak index versus Borel rank Murlak, Filip Weak index Borel rank deterministic tree automata 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Filip Murlak 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1318 urn:nbn:de:0030-drops-13182 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1318 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode