A Characterisation of Pi^0_2 Regular Tree Languages

DOI10.4230/LIPICS.MFCS.2017.56MaRDI QIDQ5111272zbMATH OpenOpenAlexFDO

Authors Filippo Cavallari, Henryk Michalewski, Michał Skrzypczak

Publication date 26 May 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/mfcs/mfcs2017.html#CavallariMS17

zbMATH Keywords

regular languagesinfinite treesRabin-Mostowski hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Deciding the Borel complexity of regular tree languages
• Regular tree languages in low levels of the Wadge hierarchy
• Computer Science Logic
• A gap property of deterministic tree languages.
• Weak index versus Borel rank

Cites work

• scientific article; zbMATH DE number 1304332 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 3186871 (Why is no real title available?)
• A gap property of deterministic tree languages.
• Alternating finite automata on \(\omega\)-words
• Automata, logics, and infinite games. A guide to current research
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Deciding the Borel complexity of regular tree languages
• Deciding the topological complexity of Büchi languages
• Deciding the weak definability of Büchi definable tree languages
• Descriptive set theoretic methods in automata theory. Decidability and topological complexity
• Index problems for game automata
• Measure Properties of Game Tree Languages
• On nondeterministic unranked tree automata with sibling constraints
• On the Topological Complexity of Weakly Recognizable Tree Languages
• Quasi-weak cost automata: a new variant of weakness
• Regular languages of infinite trees that are Boolean combinations of open sets
• The Borel hierarchy is infinite in the class of regular sets of trees
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• The Wadge Hierarchy of Deterministic Tree Languages

Cited in

(7)

• Regular tree languages in low levels of the Wadge hierarchy
• Regular languages of thin trees
• THE REGULARITY OF TWO-WAY NONDETERMINISTIC TREE AUTOMATA LANGUAGES
• On regular tree languages and deterministic pushdown automata
• Weak index versus Borel rank
• Deciding the Borel complexity of regular tree languages
• Polishness of some topologies related to word or tree automata

This page was built for publication: A Characterisation of Pi^0_2 Regular Tree Languages

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