On some sets of dictionaries whose ω ‐powers have a given

Mathematical Logic Quarterly 56 (5):452-460 (2010)

A dictionary is a set of finite words over some finite alphabet X. The omega-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [Omega-powers and descriptive set theory, JSL 2005] the complexity of the set of dictionaries whose associated omega-powers have a given complexity. In particular, he considered the sets $W({bfSi}^0_{k})$ (respectively, $W({bfPi}^0_{k})$, $W({bfDelta}_1^1)$) of dictionaries $V subseteq 2^star$ whose omega-powers are ${bfSi}^0_{k}$-sets (respectively, ${bfPi}^0_{k}$-sets, Borel sets). In this paper we first establish a new relation between the sets $W({bfSigma}^0_{2})$ and $W({bfDelta}_1^1)$, showing that the set $W({bfDelta}_1^1)$ is ``more complex' than the set $W({bfSigma}^0_{2})$. As an application we improve the lower bound on the complexity of $W({bfDelta}_1^1)$ given by Lecomte. Then we prove that, for every integer $kgeq 2$, (respectively, $kgeq 3$) the set of dictionaries $W({bfPi}^0_{k+1})$ (respectively, $W({bfSi}^0_{k+1})$) is ``more complex' than the set of dictionaries $W({bfPi}^0_{k})$ (respectively, $W({bfSi}^0_{k})$)
Keywords ω ‐power  ω ‐language  topological complexity  Borel set  Borel rank  descriptive set theory  Borel hierarchy  Infinite word  set of languages  Cantor topology
Categories (categorize this paper)
DOI 10.1002/malq.200810154
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 45,545
Through your library

References found in this work BETA

Ω-Powers and Descriptive Set Theory.Dominique Lecomte - 2005 - Journal of Symbolic Logic 70 (4):1210-1232.
Classical and Effective Descriptive Complexities of Ω-Powers.Olivier Finkel & Dominique Lecomte - 2009 - Annals of Pure and Applied Logic 160 (2):163-191.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles


Added to PP index

Total views
13 ( #643,690 of 2,280,496 )

Recent downloads (6 months)
1 ( #833,382 of 2,280,496 )

How can I increase my downloads?


My notes

Sign in to use this feature