Weak index versus Borel rank

DOI10.4230/LIPICS.STACS.2008.1318zbMATH Open1259.68112arXiv0802.2842MaRDI QIDQ4910751FDOQ4910751

Filip Murlak

Publication date: 19 March 2013

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0802.2842

Recommendations

• On the weak index problem for game automata
• Definable operations on weakly recognizable sets of trees
• A gap property of deterministic tree languages.
• Hierarchies of weak automata and weak monadic formulas
• A Characterisation of Pi^0_2 Regular Tree Languages

zbMATH Keywords

deterministic tree automataBorel rankweak index

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (4)

• Index Problems for Game Automata
• On the Weak Index Problem for Game Automata
• A gap property of deterministic tree languages.
• Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata

This page was built for publication: Weak index versus Borel rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4910751)