Classical and effective descriptive complexities of \(\omega \)-powers

DOI10.1016/j.apal.2009.02.005zbMath1170.03025MaRDI QIDQ2271988

Dominique Lecomte, Olivier Finkel

Publication date: 5 August 2009

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2009.02.005

zbMATH Keywords

Borel class; effective descriptive set theory; \(\omega \)-power; hyperarithmetical hierarchy

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03E15: Descriptive set theory

54H05: Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets)

03D45: Theory of numerations, effectively presented structures

Related Items

Polishness of some topologies related to word or tree automata, Some complete \(\omega\)-powers of a one-counter language, for any Borel class of finite rank, On some sets of dictionaries whose ω -powers have a given, Highly Undecidable Problems For Infinite Computations

Cites Work

• Descriptive set theory
• On Borel ideals
• Borel hierarchy and omega context free languages.
• Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
• Borel ranks and Wadge degrees of context free $\omega$-languages
• There Exist Some ω-Powers of Any Borel Rank
• Les propriétés de réduction et de norme pour les classes de Boréliens
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• Π₁¹ Borel sets
• ω-powers and descriptive set theory
• A Separation Theorem for ∑ 1 1 Sets
• Topological properties of omega context-free languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item