A Characterisation of Pi^0_2 Regular Tree Languages

DOI10.4230/LIPICS.MFCS.2017.56zbMATH Open1441.68118OpenAlexW2775641364MaRDI QIDQ5111272FDOQ5111272

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

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

zbMATH Keywords

regular languagesinfinite treesRabin-Mostowski hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (7)

• Regular languages of thin trees
• On regular tree languages and deterministic pushdown automata
• Deciding the Borel complexity of regular tree languages
• Regular tree languages in low levels of the Wadge hierarchy
• Weak index versus Borel rank
• THE REGULARITY OF TWO-WAY NONDETERMINISTIC TREE AUTOMATA 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)