Topological Complexity of omega-Powers : Extended Abstract

Olivier Finkel (1) , Dominique Lecomte (2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 IMJ - Institut de Mathématiques de Jussieu

This is an extended abstract presenting new results on the topological complexity of omega-powers (which are included in a paper "Classical and effective descriptive complexities of omega-powers" available from http://fr.arxiv.org/abs/0708.4176) and reflecting also some open questions which were discussed during the Dagstuhl seminar on "Topological and Game-Theoretic Aspects of Infinite Computations" 29.06.08 - 04.07.08.

Mots clés: Infinite words; omega-languages; omega-powers; Cantor topology; topological complexity; Borel sets; Borel ranks; complete sets; Wadge hierarchy; Wadge degrees; effective descriptive set theory; hyperarithmetical hierarchy

Domaines: Logique en informatique [cs.LO]; Logique [math.LO]; Complexité [cs.CC]

Olivier Finkel, Dominique Lecomte. Topological Complexity of omega-Powers : Extended Abstract. Dagstuhl Seminar on "Topological and Game-Theoretic Aspects of Infinite Computations" 29.06.08 - 04.07.08, P. Hertling, V. Selivanov, W. Thomas, W. W. Wadge, K. Wagner, Dagstuhl, Germany. ⟨ensl-00319447v2⟩