2026-07-23T04:49:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1650 2024-03-06T11:08:11Z ddc:004 open_access

Topological Complexity of omega-Powers: Extended Abstract Finkel, Olivier Lecomte, Dominique Infinite words omega-languages omega-powers Cantor topology topological complexity Borel sets Borel ranks complete sets Wadge hierarchy Wadge 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Olivier Finkel and Dominique Lecomte 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08271.7 urn:nbn:de:0030-drops-16505 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.7 eng https://creativecommons.org/licenses/by/4.0/legalcode