Classical and effective descriptive complexities of \(\omega \)-powers
From MaRDI portal
Publication:2271988
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
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
- Π11 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