Finkel, Olivier ;
Lecomte, Dominique
Topological Complexity of omegaPowers: Extended Abstract
Abstract
The operation of taking the omegapower $V^omega$ of a language $V$ is a fundamental operation over finitary languages leading to omegalanguages. Since the set $X^omega$ of infinite words over a finite alphabet $X$ can be equipped with the usual Cantor topology, the question of the topological complexity of omegapowers of finitary languages naturally arises and has been posed by Damian Niwinski (1990), Pierre Simonnet (1992), and Ludwig Staiger (1997). We investigate the topological complexity of omegapowers. We prove the following very surprising results which show that omegapowers exhibit a great opological complexity: for each nonnull countable ordinal $xi$, there exist some $Sigma^0_xi$complete omegapowers, and some $Pi^0_xi$complete omegapowers. On the other hand, the Wadge hierarchy is a great refinement of the Borel hierarchy, determined by Bill Wadge. We show that, for each ordinal $xi$ greater than or equal to 3, there are uncountably many Wadge degrees of omegapowers of Borel rank $xi +1$. Using tools of effective descriptive set theory, we prove some effective versions of the above results.
BibTeX  Entry
@InProceedings{finkel_et_al:DSP:2008:1650,
author = {Olivier Finkel and Dominique Lecomte},
title = {Topological Complexity of omegaPowers: Extended Abstract},
booktitle = {Topological and GameTheoretic Aspects of Infinite Computations},
year = {2008},
editor = {Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
number = {08271},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1650},
annote = {Keywords: Infinite words, omegalanguages, omegapowers, Cantor topology, topological complexity, Borel sets, Borel ranks, complete sets, Wadge hierarchy, Wadge}
}
05.11.2008
Keywords: 

Infinite words, omegalanguages, omegapowers, Cantor topology, topological complexity, Borel sets, Borel ranks, complete sets, Wadge hierarchy, Wadge 
Seminar: 

08271  Topological and GameTheoretic Aspects of Infinite Computations

Issue date: 

2008 
Date of publication: 

05.11.2008 