Weak index versus Borel rank

DOI10.4230/LIPICS.STACS.2008.1318MaRDI QIDQ4910751zbMATH OpenFDO

Authors Filip Murlak

Publication date 19 March 2013

Full work available at URL https://arxiv.org/abs/0802.2842, http://subs.emis.de/LIPIcs/frontdoor_48d2.html

zbMATH Keywords

Borel rankdeterministic tree automataweak index

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

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

Cited in

(7)

• A gap property of deterministic tree languages.
• Definable operations on weakly recognizable sets of trees
• On the weak index problem for game automata
• Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
• A Characterisation of Pi^0_2 Regular Tree Languages
• Index problems for game automata
• Deterministic and game separability for regular languages of infinite trees

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)