| Identifiant de l'article : |
 |
ensl-00168644, version 2 |
|
|
| Identifiant arXiv : |
|
arXiv:0708.4176 |
|
|
| Domaine : |
|
|
|
|
| Titre : |
|
Classical and Effective Descriptive Complexities of omega-Powers |
|
|
| Auteur(s) : |
|
Olivier Finkel1, 2, Dominique Lecomte3 |
|
|
| Laboratoire : |
|
| 1 : |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
| 2 : |
ELM - Équipe de Logique Mathématique |
|
| 3 : |
IMJ - Institut de Mathématiques de Jussieu |
|
|
|
| Équipe de recherche : |
|
[MC2 - Modèles de calcul et complexité] |
| Résumé : |
|
We prove that, for each non null countable ordinal alpha, there exist some Sigma^0_alpha-complete omega-powers, and some Pi^0_alpha-complete omega-powers, extending previous works on the topological complexity of omega-powers. We prove effective versions of these results. In particular, for each non null recursive ordinal alpha, there exists a recursive finitary language A such that A^omega is Sigma^0_alpha-complete (respectively, Pi^0_alpha-complete). To do this, we prove effective versions of a result by Kuratowski, describing a Borel set as the range of a closed subset of the Baire space by a continuous bijection. This leads us to prove closure properties for the classes Effective-Pi^0_alpha and Effective-Sigma^0_alpha of the hyperarithmetical hierarchy in arbitrary recursively presented Polish spaces. We apply our existence results to get better computations of the topological complexity of some sets of dictionaries considered by the second author in [Omega-Powers and Descriptive Set Theory, Journal of Symbolic Logic, Volume 70 (4), 2005, p. 1210-1232]. |
|
|
|
Langue du texte
intégral : |
|
Anglais |
|
|
| Mots-clés : |
|
omega-power – Borel class – complete – effective descriptive set theory – hyperarithmetical hierarchy. |
|
|
| Commentaire : |
|
Final Version, published in A.P.A.L. This paper is an extended version of a conference paper which appeared in the Proceedings of the 16th EACSL Annual Conference on Computer Science and Logic, CSL 07. Part of the results in this paper have been also presented at the International Conference Computability in Europe, CiE 07, Siena, Italy, June 2007. |
|
|
| Référence interne : |
|
LIP Research Report RR 2007-38 |
|
|
Récupérer au format
