Locally finite ω-languages and effective analytic sets have the same topological complexity
From MaRDI portal
Publication:2827947
DOI10.1002/malq.201400113zbMath1432.03073OpenAlexW2520058201MaRDI QIDQ2827947
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
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
- Π11 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