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

DOI10.1002/MALQ.201400113MaRDI QIDQ2827947zbMATH OpenOpenAlexFDO

Authors Olivier Finkel

Publication date 24 October 2016

Published in Mathematical Logic Quarterly (MLQ) (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) Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15)

Recommendations

• Topological complexity of locally finite \(\omega\)-languages
• Complexity of topological properties of regular \(\omega\)-languages
• Complexity of Topological Properties of Regular ω-Languages
• A topological property of rational -languages
• Topological complexity of context-free \(\omega \)-languages: a survey
• Complexity of Aperiodicity for Topological Properties of Regular ω-Languages
• Closure properties of locally finite \(\omega\)-languages
• Topology and ambiguity in \(\omega\)-context free languages
• scientific article; zbMATH DE number 60833
• Topological properties of omega context-free languages

Cites work

• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• A hierarchy of deterministic context-free \(\omega\)-languages.
• Borel hierarchy and omega context free languages.
• Borel ranks and Wadge degrees of context free $\omega$-languages
• Classical recursion theory. The theory of functions and sets of natural numbers
• Classical recursion theory. Vol. II
• Closure properties of locally finite \(\omega\)-languages
• Computer science and the fine structure of Borel sets
• Descriptive set theory
• Fine hierarchy of regular \(\omega\)-languages
• Formal languages defined by the underlying structure of their words
• Highly Undecidable Problems For Infinite Computations
• Locally finite languages
• Logic, semigroups and automata on words
• Nondeterministic Ω-Computations and the Analytical Hierarchy
• Stretchings
• The Complexity of Infinite Computations In Models of Set Theory
• Topological complexity of locally finite \(\omega\)-languages
• Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank
• -computations on Turing machines
• Π₁¹ Borel sets

Cited in

(4)

• Locally finite languages
• Classical and effective descriptive complexities of \(\omega \)-powers
• Closure properties of locally finite \(\omega\)-languages
• Topological complexity of locally finite \(\omega\)-languages

This page was built for publication: Locally finite \(\omega\)-languages and effective analytic sets have the same topological complexity

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