HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

There Exist some Omega-Powers of Any Borel Rank

Abstract : Omega-powers of finitary languages are languages of infinite words (omega-languages) in the form V^omega, where V is a finitary language over a finite alphabet X. They appear very naturally in the characterizaton of regular or context-free omega-languages. Since the set 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 Niwinski (1990), Simonnet (1992) and Staiger (1997). It has been recently proved that for each integer n > 0 , there exist some omega-powers of context free languages which are Pi^0_n-complete Borel sets, that there exists a context free language L such that L^omega is analytic but not Borel, and that there exists a finitary language V such that V^omega is a Borel set of infinite rank. But it was still unknown which could be the possible infinite Borel ranks of omega-powers. We fill this gap here, proving the following very surprising result which shows that omega-powers exhibit a great topological complexity: for each non-null countable ordinal alpha, there exist some Sigma^0_alpha-complete omega-powers, and some Pi^0_alpha-complete omega-powers.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

Contributor : Olivier Finkel Connect in order to contact the contributor
Submitted on : Monday, June 25, 2007 - 3:37:21 PM
Last modification on : Saturday, September 11, 2021 - 3:17:25 AM
Long-term archiving on: : Thursday, April 8, 2010 - 9:28:57 PM


Files produced by the author(s)


  • HAL Id : ensl-00157204, version 1
  • ARXIV : 0706.3523


Dominique Lecomte, Olivier Finkel. There Exist some Omega-Powers of Any Borel Rank. 16th EACSL Annual Conference on Computer Science and Logic, CSL 2007, September 11-15, 2007, Lausanne, Switzerland. pp.115-129. ⟨ensl-00157204⟩



Record views


Files downloads