A Characterisation of Pi^0_2 Regular Tree Languages

DOI10.4230/LIPIcs.MFCS.2017.56zbMath1441.68118OpenAlexW2775641364MaRDI QIDQ5111272

Henryk Michalewski, Filippo Cavallari, 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)

Related Items (2)

Unnamed Item ⋮ Polishness of some topologies related to word or tree automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptive set theoretic methods in automata theory. Decidability and topological complexity
• Alternating finite automata on \(\omega\)-words
• The Borel hierarchy is infinite in the class of regular sets of trees
• A gap property of deterministic tree languages.
• Automata, logics, and infinite games. A guide to current research
• Measure Properties of Game Tree Languages
• Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• Deciding the topological complexity of Büchi languages *
• Deciding the Borel Complexity of Regular Tree Languages
• Index Problems for Game Automata
• On the Topological Complexity of Weakly Recognizable Tree Languages
• Decidability of Second-Order Theories and Automata on Infinite Trees
• The Wadge Hierarchy of Deterministic Tree Languages

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