Finkel, Olivier ;
Lecomte, Dominique
Topological Complexity of omega-Powers: Extended Abstract
Abstract
The operation of taking the omega-power $V^omega$ of a language $V$ is a fundamental operation over finitary languages leading to omega-languages. 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 omega-powers 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 omega-powers. We prove the following very surprising results which show that omega-powers exhibit a great opological complexity: for each non-null countable ordinal $xi$, there exist some $Sigma^0_xi$-complete omega-powers, and some $Pi^0_xi$-complete omega-powers. 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 omega-powers 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 omega-Powers: Extended Abstract},
booktitle = {Topological and Game-Theoretic 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 = {1862-4405},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1650},
annote = {Keywords: Infinite words, omega-languages, omega-powers, Cantor topology, topological complexity, Borel sets, Borel ranks, complete sets, Wadge hierarchy, Wadge}
}
|
Keywords: |
|
Infinite words, omega-languages, omega-powers, Cantor topology, topological complexity, Borel sets, Borel ranks, complete sets, Wadge hierarchy, Wadge |
|
Seminar: |
|
08271 - Topological and Game-Theoretic Aspects of Infinite Computations
|
|
Issue date: |
|
2008 |
|
Date of publication: |
|
05.11.2008 |
05.11.2008
