On the Strength of Unambiguous Tree Automata

DOI10.1142/S012905411842011XzbMath1403.68119OpenAlexW2888133868MaRDI QIDQ4683238

Michał Skrzypczak, Henryk Michalewski

Publication date: 20 September 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905411842011x

zbMATH Keywords

infinite treesunambiguityRabin-Mostowski index

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Choice functions and well-orderings over the infinite binary tree
• Alternating finite automata on \(\omega\)-words
• The Borel hierarchy is infinite in the class of regular sets of trees
• Ambiguous classes in \(\mu\)-calculi hierarchies
• Unambiguous Büchi Is Weak
• Forms of Determinism for Automata (Invited Talk)
• On Recognizable Tree Languages Beyond the Borel Hierarchy
• Deciding the topological complexity of Büchi languages *
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• On the Topological Complexity of Weakly Recognizable Tree Languages
• The Wadge Hierarchy of Deterministic Tree Languages

This page was built for publication: On the Strength of Unambiguous Tree Automata