Locally finite ω-languages and effective analytic sets have the same topological complexity

DOI10.1002/malq.201400113zbMath1432.03073OpenAlexW2520058201MaRDI QIDQ2827947

Olivier Finkel

Publication date: 24 October 2016

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.201400113

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Topological complexity of locally finite \(\omega\)-languages
• Fine hierarchy of regular \(\omega\)-languages
• Descriptive set theory
• Classical recursion theory. The theory of functions and sets of natural numbers
• \(\omega\)-computations on Turing machines
• Classical recursion theory. Vol. II
• A hierarchy of deterministic context-free \(\omega\)-languages.
• Borel hierarchy and omega context free languages.
• Logic, semigroups and automata on words
• Closure properties of locally finite \(\omega\)-languages
• Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
• The Determinacy of Context-Free Games
• The Complexity of Infinite Computations In Models of Set Theory
• Borel ranks and Wadge degrees of context free $\omega$-languages
• Highly Undecidable Problems For Infinite Computations
• Nondeterministic Ω-Computations and the Analytical Hierarchy
• Π₁¹ Borel sets
• Formal languages defined by the underlying structure of their words
• Stretchings
• Locally finite languages
• Computer science and the fine structure of Borel sets