Classical and effective descriptive complexities of ω-powers
| Autor: | Dominique Lecomte, Olivier Finkel |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
medicine.medical_specialty Logic Recursive ordinal ω-power Baire space Effective descriptive set theory Borel class Combinatorics Mathematics::Logic Projective hierarchy Complete Borel hierarchy Hyperarithmetical hierarchy medicine Polish space Borel set Descriptive set theory Mathematics |
| Zdroj: | Annals of Pure and Applied Logic. 160:163-191 |
| ISSN: | 0168-0072 |
| DOI: | 10.1016/j.apal.2009.02.005 |
| Popis: | We prove that, for each countable ordinal ξ≥1, there exist some Σξ0-complete ω-powers, and some Πξ0-complete ω-powers, extending previous works on the topological complexity of ω-powers [O. Finkel, Topological properties of omega context free languages, Theoretical Computer Science 262 (1–2) (2001) 669–697; O. Finkel, Borel hierarchy and omega context free languages, Theoretical Computer Science 290 (3) (2003) 1385–1405; O. Finkel, An omega-power of a finitary language which is a borel set of infinite rank, Fundamenta informaticae 62 (3–4) (2004) 333–342; D. Lecomte, Sur les ensembles de phrases infinies constructibles a partir d’un dictionnaire sur un alphabet fini, Séminaire d’Initiation a l’Analyse, 1, année 2001–2002; D. Lecomte, Omega-powers and descriptive set theory, Journal of Symbolic Logic 70 (4) (2005) 1210–1232; J. Duparc, O. Finkel, An ω-Power of a Context-Free Language Which Is Borel Above Δω0, in: S. Bold, B. Löwe, T. Räsch, J. van Benthem (Eds.), in the Proceedings of the international conference foundations of the formal sciences V : Infinite Games, November 26th to 29th, 2004, Bonn, Germany, in: Studies in Logic, vol. 11, College Publications at King’s College, 2007, pp. 109–122]. We prove effective versions of these results; in particular, for each recursive ordinal ξ |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect