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

✍ Scribed by Olivier Finkel

• Publisher: John Wiley and Sons
• Year: 2010
• Tongue: English
• Weight: 147 KB
• Volume: 56
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.200810154

✦ Synopsis

A dictionary is a set of finite words over some finite alphabet X. The ω-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V . Lecomte studied in [10] the complexity of the set of dictionaries whose associated ω-powers have a given complexity. In particular, he considered the sets

In this paper we first establish a new relation between the sets W(Σ 0 2 ) and W(Δ 1 1 ), showing that the set W(Δ 1 1 ) is "more complex" than the set W(Σ 0 2 ). As an application we improve the lower bound on the complexity of W(Δ 1 1 ) given by Lecomte, showing that

Then we prove that, for every integer k ≥ 2 (respectively, k ≥ 3), the set of dictionaries W(Π 0 k+1 ) (respectively, W(Σ 0 k+1 )) is "more complex" than the set of dictionaries W(Π 0 k ) (respectively, W(Σ 0 k )) .