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

DOI10.1002/MALQ.201400113zbMATH Open1432.03073OpenAlexW2520058201MaRDI QIDQ2827947FDOQ2827947

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

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 \(\omega\)-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

Mathematics Subject Classification ID

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

Cites Work

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

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)