On recognizable tree languages beyond the Borel hierarchy

DOI10.3233/FI-2009-151MaRDI QIDQ3400555zbMATH OpenFDO

Authors P. Simonnet, Olivier Finkel

Publication date 5 February 2010

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/FI-2009-151

zbMATH Keywords

Borel hierarchyCantor topologycomplete setsdifference hierarchy of analytic setsgame tree languageinfinite treesregular tree languagetopological complexitytree automatonunambiguous tree automaton

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15) Formal languages and automata (68Q45)

Recommendations

• An upper bound on the complexity of recognizable tree languages
• On the Borel inseparability of game tree languages
• Deciding the Borel complexity of regular tree languages
• Computer Science Logic
• On the Topological Complexity of Weakly Recognizable Tree Languages

Cited in

(16)

• A gap property of deterministic tree languages.
• Characterizations of recognizable weighted tree languages by logic and bimorphisms
• Unambiguous Büchi Is Weak
• On topological completeness of regular tree languages
• Regular languages of thin trees
• On the topological complexity of tree languages
• Deciding the topological complexity of Büchi languages
• On the strength of unambiguous tree automata
• Unambiguous tree languages are topologically harder than deterministic ones
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• Deciding the Borel complexity of regular tree languages
• On the Borel inseparability of game tree languages
• On the Topological Complexity of Weakly Recognizable Tree Languages
• Continuous separation of game languages
• A tentative approach for the Wadge-Wagner hierarchy of regular tree languages of index \([0,2]\)
• An upper bound on the complexity of recognizable tree languages

This page was built for publication: On recognizable tree languages beyond the Borel hierarchy

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