An upper bound on the complexity of recognizable tree languages

DOI10.1051/ITA/2015002MaRDI QIDQ5501862zbMATH OpenOpenAlexFDO

Authors Dominique Lecomte, P. Simonnet, 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

Borel hierarchyCantor topologygame quantifierinfinite treesprovably-\(\Delta^{1}_{2}\)regular tree languagetopological complexitytree automatonuniversal setswadge classeswadge degrees

Mathematics Subject Classification ID

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

Abstract: The third author noticed in his 1992 PhD Thesis [Sim92] that every regular tree language of infinite trees is in a class $$ for some natural number $ngeq1$, where $Game$ is the game quantifier. We first give a detailed exposition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel subsets of the Cantor space $2^{o}mega$ into the class $$, and the notions of Wadge degree and Veblen function, we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual $$.

Recommendations

• On recognizable tree languages beyond the Borel hierarchy
• Deciding the Borel complexity of regular tree languages
• On the Topological Complexity of Weakly Recognizable Tree Languages
• On the topological complexity of tree languages
• The Wadge Hierarchy of Deterministic Tree Languages

Cites work

• A gap property of deterministic tree languages.
• Computer Science Logic
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Deciding the Borel complexity of regular tree languages
• scientific article; zbMATH DE number 3652325 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• Measure Properties of Game Tree Languages
• On recognizable tree languages beyond the Borel hierarchy
• On the topological complexity of tree languages
• Parallel Machine Scheduling with Uncertain Communication Delays
• Quasi-bounded trees and analytic inductions
• 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 Mathematical Import of Zermelo's Well-Ordering Theorem
• The Wadge Hierarchy of Deterministic Tree Languages
• Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank

Cited in

(9)

• The complexity of the exponential output size problem for top-down and bottom-up tree transducers
• Wadge-Wagner hierarchies
• Measure properties of regular sets of trees
• On the topological complexity of tree languages
• ON THE COMPLEXITY OF RECOGNIZABLE ω-TREE SETS AND NERODE THEOREM
• On recognizable tree languages beyond the Borel hierarchy
• On the Complexity of the Syntax of Tree Languages
• Deciding the Borel complexity of regular tree languages
• On the Topological Complexity of Weakly Recognizable Tree Languages

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

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