An upper bound on the complexity of recognizable tree languages

DOI10.1051/ita/2015002zbMath1373.03066arXiv1503.02840OpenAlexW2963989869MaRDI QIDQ5501862

Pierre Simonnet, Dominique Lecomte, Olivier Finkel

Publication date: 14 August 2015

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.02840

zbMATH Keywords

topological complexityBorel hierarchyregular tree languageinfinite treesuniversal setstree automatonCantor topologygame quantifierwadge degreesprovably-\(\Delta^{1}_{2}\)wadge classes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive set theory (03E15) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Measure properties of regular sets of trees ⋮ Wadge-Wagner hierarchies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Borel hierarchy is infinite in the class of regular sets of trees
• A gap property of deterministic tree languages.
• Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
• The Determinacy of Context-Free Games
• Measure Properties of Game Tree Languages
• Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets
• On Recognizable Tree Languages Beyond the Borel Hierarchy
• The Mathematical Import of Zermelo's Well-Ordering Theorem
• Parallel Machine Scheduling with Uncertain Communication Delays
• Deciding the Borel Complexity of Regular Tree Languages
• Computer Science Logic
• Quasi-bounded trees and analytic inductions
• Decidability of Second-Order Theories and Automata on Infinite Trees
• The Wadge Hierarchy of Deterministic Tree Languages

This page was built for publication: An upper bound on the complexity of recognizable tree languages