# Some Regular $\omega$-Powers in the Hausdorff-Kuratowski Hierarchy

Olivier Finkel, Johan Girardot, Dominique Lecomte

<figure><img src="image_1.png" /></figure>

## To cite this version:

Olivier Finkel, Johan Girardot, Dominique Lecomte. Some Regular $\omega$-Powers in the Hausdorff-Kuratowski Hierarchy. 2024. hal-05335660

HAL Id: hal-05335660

https://hal.science/hal-05335660v1

Preprint submitted on 28 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Some Regular $\omega$-Powers in the Hausdorff-Kuratowski Hierarchy

Olivier Finkel¹, Johan Girardot², Dominique Lecomte³

¹CNRS, Université Paris Cité and Sorbonne Université,
IMJ-PRG, F-75013 Paris, France.

Olivier.Finkel@math.univ-paris-diderot.fr

²Institut Polytechnique de Paris, Ecole Polytechnique,
LIX Laboratory 91128 Palaiseau Cedex

²Université Paris Cité and Sorbonne Université, CNRS,
IMJ-PRG, F-75013 Paris, France.

²Université Sorbonne Paris Nord, LIPN, Institut Galilée,
99 Avenue Jean-Baptiste Clément 93430 Villetaneuse, France.

johan.girardot@ens-paris-saclay.fr

³Sorbonne Université and Université Paris Cité, CNRS,
IMJ-PRG, F-75005 Paris, France.

Dominique.Lecomte@upmc.fr

³Université de Picardie, I.U.T. de l'Oise, site de Creil,
13, allée de la faïencerie, 60100 Creil, France.

December 12, 2024

## Abstract

Fix a finite alphabet $X$ having at least two letters, and a natural number $n$. We denote by $D_n(\Pi_2^0)$ the class of differences of $n \Pi_2^0$ subsets of the Cantor space $X^\omega$, and by $D_n^-(\Pi_2^0)$ the class of complements of sets in $D_n(\Pi_2^0)$. We prove the existence of finitary regular languages $U_n$ and $V_n$ such that $(U_n)^\omega$ is $D_{2n+1}(\Pi_2^0)$-complete and $(V_n)^\omega$ is $D_{2n+2}^-(\Pi_2^0)$-complete.

Keywords: Regular languages of finite or infinite words; omega-powers; Topology; Hierarchy of differences of $\Pi_2^0$-sets; Wadge-Wagner class; Complete sets.
# 1 Introduction

In the sixties, in order to prove the decidability of the monadic second order theory of one successor over the integers, Büchi studied acceptance of infinite words by finite automata, with the now called Büchi acceptance condition. Since then, a lot of work has been done on regular $\omega$-languages, accepted by Büchi automata, or by some other variants of automata over infinite words, like Muller or Rabin automata, see [Tho90, Sta97a, PP04].

The class of regular $\omega$-languages, those accepted by Büchi or Muller automata, is the $\omega$-Kleene closure of the family of regular finitary languages. Recall that if $\Sigma$ is an alphabet and $L \subseteq \Sigma^*$ is a finitary language over $\Sigma$, the $\omega$-power $L^\omega$ of $L$ is the set of the infinite words constructible with $L$ by concatenation, i.e.,

$$L^\omega := \{ w_0 w_1 \dots \in \Sigma^\omega \mid \forall i \in \omega \ w_i \in L \}.$$

The $\omega$-Kleene closure of a class $C$ of languages of finite words over finite alphabets is the class of $\omega$-languages of the form $\bigcup_{1 \le j \le n} U_j \cdot V_j^\omega$, for some finitary languages $U_j$ and $V_j$ in the class $C$, $1 \le j \le n$.

Note that we denote here by $L^\omega$ the $\omega$-power associated with $L$, as usually in Theoretical Computer Science papers, as in [Sta97a, Fin01, Fin03, FL07]. It has also been denoted by $L^\infty$ in some other papers, as in [Lec05, FL09], and in the recent survey paper [FL20].

Note that the operation of taking the $\omega$-power of a finitary language also appears in the characterization of the class of context-free $\omega$-languages as the $\omega$-Kleene closure of the family of context-free finitary languages, [Sta97a].

Therefore, the operation $L \to L^\omega$ is a fundamental operation over finitary languages leading to $\omega$-languages, and it is important to understand its complexity in the study of $\omega$-languages accepted by various automata. Since the set $\Sigma^\omega$ of infinite words over a finite alphabet $\Sigma$ can be equipped with the usual Cantor topology, the question of the topological complexity of $\omega$-powers of finitary languages naturally arises and was raised by Niwinski [Niw90], Simonnet [Sim92], and Staiger [Sta97a].

In particular, the $\omega$-powers have recently been studied from the perspective of Descriptive Set Theory in several papers [Fin01, Fin03, Fin04, Lec05, DF07, FL07, FL09, FL21, FL20].

In the present paper, we focus on the study of the $\omega$-powers of regular languages. These $\omega$-powers have been studied by Litovsky and Timmerman in [LT87, Sta97a], where they proved that one can decide whether a regular $\omega$-language is an $\omega$-power, and moreover that if a regular $\omega$-language $L$ is an $\omega$-power, then there exists a regular finitary language $V$ such that $L = V^\omega$.
The topological complexity of regular $\omega$-languages is now well known. Every regular $\omega$-language is a finite boolean combination of Borel $\Pi_2^0$-sets, hence a $\Delta_3^0$-set. On the other hand, the Wadge hierarchy of Borel sets on a Cantor space is a great refinement of the Borel hierarchy, defined via reductions by continuous functions, and determined by Wadge using some infinite games now called Wadge games, see [Wad83]. The trace of the Wadge hierarchy on the class of $\omega$-regular languages is called the Wagner hierarchy. It has been completely described by Wagner in [Wag79]. Its length is the (countable) ordinal $\omega^\omega$. Wagner gave an automaton-like characterization of this hierarchy, based on the notions of a chain and a superchain in a Muller automaton, together with an algorithm to compute the Wadge (Wagner) degree of any given $\omega$-regular language, see also [Sel98, Sel08b, Sel08a, Sim92]. A coarser hierarchy of regular $\omega$-languages, which is in fact the hierarchy of finite differences of $\Pi_2^0$-sets, has been studied by Barua in [Bar92].

Let $X$ be a finite alphabet having at least two letters, and $n$ be a natural number. We denote by $D_n(\Pi_2^0)$ the class of differences of $n \ \Pi_2^0$ subsets of the Cantor space $X^\omega$, and by $D_n^-(\Pi_2^0)$ the class of complements of sets in $D_n(\Pi_2^0)$. In this paper, we use the notion of a chain in a Muller automaton and the work of Barua and Wagner to prove the existence of finitary regular languages $U_n$ and $V_n$ such that $(U_n)^\omega$ is $D_{2n+1}(\Pi_2^0)$-complete and $(V_n)^\omega$ is $D_{2n+2}^-(\Pi_2^0)$-complete

Note that the $\omega$-powers we obtain are also the first examples of $\omega$-powers having these complexities (except for $n=0$), even for non regular ones. Moreover, up to our knowledge, the only known classes of topological complexity of $\omega$-powers inside the class $\Delta_3^0 \setminus \Delta_2^0$ were $\Pi_2^0$, $D_2^-(\Pi_2^0)$ (note that $\omega$-powers having these complexities can be regular, see [Lec05, Sta97b]), and also $\Sigma_2^0$ (an $\omega$-power of a language of a 1-counter automaton having this complexity is given in [FL09]).

On the other hand, O. Finkel and D. Lecomte recently studied $\Delta_2^0 \omega$-powers in [FL24] where it is proved that, for each natural number $n$, there are some regular finitary languages $W_n$ and $W'_n$ such that the $\omega$-power $W_n^\omega$ (respectively, $W_n'^\omega$) is $D_n(\Sigma_1^0)$-complete (respectively, $D_n^-(\Sigma_1^0)$-complete). Moreover there also exist some regular $\omega$-powers which are complete for the auto-dual classes $D_{2n+1}(\Sigma_1^0) \oplus \tilde{D}_{2n+1}(\Sigma_1^0)$.

The paper is organized as follows. We recall basic notions about automata and topology in Section 2. Our main results are proved in Section 3. Some concluding remarks are given in Section 4.
## 2 Basic notions

We assume the reader to be familiar with the theory of formal (ω)-languages [Tho90, Sta97a]. We recall some usual notations in formal language theory.

When $\Sigma$ is a finite alphabet, a non-empty finite word over $\Sigma$ is any sequence $x = a_1...a_k$, where $a_i \in \Sigma$ for $i = 1, ..., k$, and $k \ge 1$ is an integer. The length of $x$ is $|x| = k$.

The set of finite words (including the empty word $\varepsilon$ whose length is zero) over $\Sigma$ is denoted $\Sigma^*$, and $\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}$ is the set of non-empty finite words over $\Sigma$.

The first infinite ordinal is $\omega$. An $\omega$-word over $\Sigma$ is an $\omega$-sequence $a_1...a_n...$, where $a_i \in \Sigma$ for any integer $i \ge 1$. When $\sigma$ is an $\omega$-word over $\Sigma$, we write $\sigma = \sigma(1)\sigma(2)...\sigma(n)...$, where $\sigma(i) \in \Sigma$ for any $i$, and $\sigma[n] = \sigma(1)\sigma(2)...\sigma(n)$.

The usual concatenation product of two finite words $u$ and $v$ is denoted by $u \cdot v$, sometimes just $uv$. This product is extended to the product of a finite word $u$ and an $\omega$-word $v$. The infinite word $u \cdot v$ is then the $\omega$-word such that $(u \cdot v)(k) = u(k)$ if $k \le |u|$, and $(u \cdot v)(k) = v(k - |u|)$ if $k > |u|$. The concatenation product can be extended in an obvious way to the concatenation of an infinite sequence of finite words. The concatenation of a set $U$ of finite words with a set $V$ of infinite words is the set of infinite words $U \cdot V = \{u \cdot v \mid u \in U \text{ and } v \in V\}$. If $u$ is a finite word and $V$ is a set of infinite words then $u \cdot V = \{u \cdot v \mid v \in V\}$. If $U \subseteq \Sigma^*$, then we define $U^1 = U$ and, for any integer $n \ge 1$, $U^{n+1} = U^n \cdot U$. Then $U^+ = \bigcup_{n \ge 1} U^n$ and $U^* = U^+ \cup \{\varepsilon\}$.

The prefix relation is denoted by $\sqsubseteq$: a finite word $u$ is a prefix of a finite word $v$ (respectively, an infinite word $v$), denoted $u \sqsubseteq v$, if and only if there exists a finite word $w$ (respectively, an infinite word $w$), such that $v = u \cdot w$. For a finite or infinite word $v$ we denote by $\text{Pref}(v)$ the set of prefixes of $v$, and for a set $L$ of finite or infinite words we set $\text{Pref}(L) = \bigcup_{v \in L} \text{Pref}(v)$.

The set of $\omega$-words over the alphabet $\Sigma$ is denoted by $\Sigma^\omega$. An $\omega$-language over $\Sigma$ is a subset of $\Sigma^\omega$.

**Definition 1** : A finite state machine (FSM) is a quadruple

$$ \mathcal{M} = (Q, \Sigma, \delta, q_0), $$

where $Q$ is a finite set of states, $\Sigma$ is a finite input alphabet, $q_0 \in Q$ is the initial state and $\delta$ is a mapping (which may be partial) from $Q \times \Sigma$ into $2^Q$. A FSM is called deterministic iff $\delta : Q \times \Sigma \to \{\{q\} \mid q \in Q\}$. (As usual, by a clear identification, we might consider in that case that $\delta : Q \times \Sigma \to Q$).
A Büchi automaton (BA) is a quintuplet $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ where $M = (Q, \Sigma, \delta, q_0)$ is a finite state machine and $F \subseteq Q$ is the set of final states.

A Muller automaton (MA) is a quintuplet $\mathcal{A} = (Q, \Sigma, \delta, q_0, \mathcal{F})$ where $M = (Q, \Sigma, \delta, q_0)$ is a FSM and $\mathcal{F} \subseteq 2^Q$ is the collection of designated state sets.

A Büchi or Muller automaton is said to be deterministic if the associated FSM is deterministic.

A deterministic Büchi or Muller automaton is said to be complete iff the transition function $\delta: Q \times \Sigma \to Q$ of the associated FSM is a total function. In that case the transition function $\delta$ can be naturally extended to a function $\delta: Q \times \Sigma^+ \to Q$ by setting $\delta(q, ua) = \delta(\delta(q, u), a)$ for every $a \in \Sigma$ and $u \in \Sigma^+$. We shall also write $\delta^F(q, u) = q'$ if $\delta(q, u) = q'$ and the set of states entered by the automaton reading $u$ from state $q$ is equal to $F$ (which includes $q$ and $q'$).

Let $\sigma = a_1a_2\dots a_n\dots$ be an $\omega$-word over $\Sigma$. A sequence $r = q_1q_2\dots q_n\dots$ of states is called an (infinite) run of $M = (Q, \Sigma, \delta, q_0)$ on $\sigma$, starting in state $p$, iff $q_1 = p$, and $q_{i+1} \in \delta(q_i, a_i)$ for each $i \ge 1$. When a run $r$ of $M$ on $\sigma$ starts with the state $q_0$, we call it simply “a run of $M$ on $\sigma$”. For every (infinite) run $r = q_1q_2\dots q_n\dots$ of $M$, $\text{In}(r)$ is the set of states in $Q$ entered by $M$ infinitely many times in $r$:

$$ \text{In}(r) = \{q \in Q \mid \exists^{\infty} i \ge 1 \ q_i = q\}. $$

If $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ is a BA, the $\omega$-language accepted by $\mathcal{A}$ is

$$ L(\mathcal{A}) = \{\sigma \in \Sigma^{\omega} \mid \text{there is a run } r \text{ of } \mathcal{A} \text{ on } \sigma \text{ such that } \text{In}(r) \cap F \neq \emptyset\}. $$

If $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ is a MA, the $\omega$-language accepted by $\mathcal{A}$ is

$$ L(\mathcal{A}) = \{\sigma \in \Sigma^{\omega} \mid \text{there is a run } r \text{ of } \mathcal{A} \text{ on } \sigma \text{ such that } \text{In}(r) \in \mathcal{F}\}. $$

By R. Mc Naughton's Theorem, see [PP04], the expressive power of deterministic MA (DMA) is equal to the expressive power of non deterministic MA, which is also equal to the expressive power of non deterministic BA. An $\omega$-language $L$ accepted by a MA or a BA is called a regular $\omega$-language.

Recall that, from a Büchi (respectively, Muller) automaton $\mathcal{A}$, one can effectively construct a deterministic Muller (respectively, non-deterministic Büchi) automaton $\mathcal{B}$ such that $L(\mathcal{A}) = L(\mathcal{B})$.

One way to study the complexity of $\omega$-languages accepted by various automata is to study their topological complexity.

We assume the reader to be familiar with basic notions of topology which may be found in [Kec95, Sta97a, PP04]. If $X$ is a finite alphabet containing
at least two letters, then the set $X^\omega$ of infinite words over $X$ may be equipped
with the product topology of the discrete topology on $X$. This topology is
induced by a natural metric, called the *prefix metric*, and defined as follows.
For $u \neq v \in X^\omega$, we set $\delta(u, v) = 2^{-l_{\text{pref}(u,v)}}$, where $l_{\text{pref}(u,v)}$ is the first
natural number $n$ such that the $u(n+1)$ is different from $v(n+1)$. The
topological space $X^\omega$ is a Cantor space. The open sets of $X^\omega$ are the sets
of the form $W \cdot X^\omega$, where $W \subseteq X^*$. A set $L \subseteq X^\omega$ is a closed set iff its
complement $X^\omega - L$ is an open set. Closed sets are characterized as follows.

**Proposition 2** A set $L \subseteq X^\omega$ is a closed subset of $X^\omega$ iff, for every $\sigma \in X^\omega$,
$\text{Pref}(\sigma) \subseteq \text{Pref}(L)$ implies that $\sigma \in L$.

We now define the next classes of the Borel hierarchy:

**Definition 3** The classes $\Sigma_n^0$ and $\Pi_n^0$ of the Borel Hierarchy on the topological space $X^\omega$ are defined as follows: $\Sigma_1^0$ is the class of open subsets of $X^\omega$, $\Pi_1^0$ is the class of closed subsets of $X^\omega$, and, for any integer $n \ge 1$, $\Sigma_{n+1}^0$ is the class of countable unions of $\Pi_n^0$-subsets of $X^\omega$, and $\Pi_{n+1}^0$ is the class of countable intersections of $\Sigma_n^0$-subsets of $X^\omega$.

It turns out that there is a characterization of $\Pi_2^0$-subsets of $X^\omega$, involving the following notion, see [Sta97a, PP04].

**Definition 4** For $W \subseteq X^*$, we set

$$
W^{\delta} = \{ \sigma \in X^{\omega} \mid \exists^{\infty} i \text{ such that } \sigma[i] \in W \}.
$$

$(\sigma \in W^{\delta} \text{ iff } \sigma \text{ has infinitely many prefixes in } W.)$

We can then state the following proposition.

**Proposition 5** A subset $L$ of $X^\omega$ is a $\Pi_2^0$-subset of $X^\omega$ iff there exists a set $W \subseteq X^*$ such that $L = W^\delta$.

We can go further by considering the Hausdorff-Kuratowski hierarchy
on a Cantor space $X^\omega$, which is the hierarchy of differences of $\Pi_2^0$-subsets
of $X^\omega$. We now give the definition for the finite ranks of this hierarchy.

**Definition 6** Let $X^\omega$ be a Cantor space, and $n$ be a natural number. A subset $L$ of $X^\omega$ is in the class $D_{n+1}(\Pi_2^0)$ if and only if there is a decreasing sequence $(G_j)_{j \le n}$ of $\Pi_2^0$-subsets of $X^\omega$ such that

$$
L = \bigcup_{j \le n; j \text{ even}} G_j - G_{j+1}.
$$

The class $D_n^-(\Pi_2^0)$ is the class of complements of sets in $D_n(\Pi_2^0)$.
The difference hierarchy is also defined for transfinite levels, but we shall
not need them in the sequel.

It is easy to see, using the above characterization of Π<sub>2</sub><sup>0</sup>-sets, that every
ω-language accepted by a deterministic Büchi automaton is a Π<sub>2</sub><sup>0</sup>-set. Thus
every regular ω-language is a finite Boolean combination of Π<sub>2</sub><sup>0</sup>-sets, because
it is accepted by a deterministic Muller automaton. This implies that it is a
finite boolean combination of ω-languages accepted by deterministic Büchi
automata. Moreover, the Boolean combinations of Π<sub>2</sub><sup>0</sup>-sets are exactly the
sets which are finite differences of Π<sub>2</sub><sup>0</sup>-sets.

Landweber studied the topological properties of regular ω-languages in
[Lan69]. He characterized the regular ω-languages in the Borel classes Σ<sub>1</sub><sup>0</sup>,
Π<sub>1</sub><sup>0</sup>, Σ<sub>2</sub><sup>0</sup>, Π<sub>2</sub><sup>0</sup>, and proved that one can decide, for an effectively given regular
ω-language L, whether L is in Σ<sub>1</sub><sup>0</sup>, Π<sub>1</sub><sup>0</sup>, Σ<sub>2</sub><sup>0</sup> or Π<sub>2</sub><sup>0</sup>. In particular, it turns
out that a regular ω-language is in the class Π<sub>2</sub><sup>0</sup> iff it is accepted by a
deterministic Büchi automaton.

We now recall the definition of the Wadge reducibility and the Wadge
hierarchy on a Cantor space.

**Definition 7 (Wadge [Wad83])** Let X, Y be two finite alphabets, L be a subset of X<sup>ω</sup>, and L' be a subset of Y<sup>ω</sup>. We say that L is Wadge reducible to L' (L ≤<sub>W</sub> L') iff there is a continuous function f : X<sup>ω</sup> → Y<sup>ω</sup>, such that L = f<sup>-1</sup>(L'). The sets L and L' are Wadge equivalent iff L ≤<sub>W</sub> L' and L' ≤<sub>W</sub> L. This will be denoted by L ≡<sub>W</sub> L'. And we shall say that L <<sub>W</sub> L' iff L ≤<sub>W</sub> L' and L' ≤<sub>W</sub> L. A set L ⊆ X<sup>ω</sup> is said to be self dual iff L ≡<sub>W</sub> L<sup>-</sup>, otherwise it is said to be non self dual.

The relation $\le_W$ is reflexive and transitive, and $\equiv_W$ is an equivalence relation. The equivalence classes of $\equiv_W$ are called Wadge degrees. The Wadge hierarchy WH is the class of Borel subsets of a set $X^\omega$, where X is a finite set, equipped with $\le_W$ and with $\equiv_W$.

A function $f$ as in Definition 7 is called a continuous reduction of $L$ to $L'$. Intuitively it means that $L$ is less complicated than $L'$ because, in order to check whether $x \in L$, it suffices to check whether $f(x) \in L'$, where $f$ is a continuous function. Hence the Wadge degree of an $\omega$-language is a measure of its topological complexity. The Wadge class of a set $L \subseteq X^\omega$ is equal to $[L] = \{L' \subseteq Y^\omega \mid Y$ is a finite alphabet and $L' \le_W L\}$. The set $L$ is then a complete set for the class $[L]$, i.e., every set in $[L]$ is continuously reducible to $L$. Recall that each Borel class $\Sigma_n^0$ and $\Pi_n^0$ is a Wadge class (a similar result holds for Borel classes of transfinite ranks). Also, every class $D_n(\Pi_2^0)$ or $D_n^-(\Pi_2^0)$ is a Wadge class. In particular, all these classes admit complete sets.

Note that, in the above definition, we consider that a subset $L \subseteq X^\omega$ is
given together with the alphabet $X$.
There is a close relationship between Wadge reducibility and particular infinite 2-player games now called Wadge games. Using these games, Wadge proved the following fundamental result.

**Theorem 8 (Wadge, Martin-Monk)** Let $X$ be a finite alphabet having at least two letters. Up to taking complement and $\equiv_W$, the class of Borel subsets of $X^\omega$ is a well ordered hierarchy. There is an ordinal $|WH|$, called the length of the hierarchy, and a map $d_W^0$ from $WH$ onto $|WH| - \{0\}$, such that, for all $L, L' \subseteq X^\omega$, $d_W^0 L < d_W^0 L'$ iff $L <_W L'$, and $d_W^0 L = d_W^0 L'$ iff $[L \equiv_W L' \text{ or } L \equiv_W L'^-]$.

Let $\omega_1$ be the first uncountable ordinal. The Wadge hierarchy of Borel sets of finite rank has length $^1\varepsilon_0$, where $^1\varepsilon_0$ is the limit of the ordinals $\alpha_n$ defined by $\alpha_1 = \omega_1$, and $\alpha_{n+1} = \omega_1^{\alpha_n}$ if $n \ge 1$ an integer. The ordinal $^1\varepsilon_0$ is the first fixed point of the ordinal exponentiation of base $\omega_1$. The Wadge hierarchy of $\Delta_2^0$-sets has length $\omega_1$ and the length of the Wadge hierarchy of boolean combinations of $\Pi_2^0$-sets is equal to the ordinal $\omega_1^\omega$. The length of the whole Wadge hierarchy of Borel sets is a huge ordinal, with regard to the ordinal $^1\varepsilon_0$. We refer the interested reader to [Wad83, Dup01] for a description of this ordinal, using the Veblen functions.

On the other hand, the trace of the Wadge hierarchy on the class of $\omega$-regular languages is called the Wagner hierarchy. It has been completely described by Wagner in [Wag79]. Its length is the (countable) ordinal $\omega^\omega$. Wagner gave an automaton-like characterization of this hierarchy, based on the notions of a chain and a superchain, together with an algorithm to compute the Wadge (Wagner) degree of any given $\omega$-regular language, see also [Sel98, Sel08b, Sel08a, Sim92]. Wagner considered complete deterministic Muller automata in his study [Wag79]. We now recall the notions of an essential set and of (alternating) chains in such an automaton.

**Definition 9 (Wagner [Wag79])** Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, \mathcal{F})$ be a complete deterministic Muller automaton. The set of essential sets of the automaton $\mathcal{A}$ is $M(\mathcal{A}) = \{F' \subseteq Q \mid L((Q, \Sigma, \delta, q_0, \{F'\})) \neq \emptyset\}$, i.e. $M(\mathcal{A})$ is the set of subsets $F'$ of $Q$ for which we can find an infinite word $\sigma \in \Sigma^\omega$ and a run $r$ on $\sigma$ (which is then the unique run on $\sigma$) such that $\text{In}(r) = F'$. The positive (or accepting) essential sets are those belonging to $\mathcal{F}$ while the negative (or rejecting) essential sets are those which do not belong to $\mathcal{F}$. We set $M^+(\mathcal{A}) = M(\mathcal{A}) \cap \mathcal{F}$ and $M^-(\mathcal{A}) = M(\mathcal{A}) \cap (2^Q \setminus \mathcal{F}) = M(\mathcal{A}) \setminus M^+(\mathcal{A})$.

**Definition 10 (Wagner [Wag79])** Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, \mathcal{F})$ be a complete deterministic Muller automaton. An alternating chain of $\mathcal{A}$ is an increasing sequence

$$F_1 \subseteq F_2 \subseteq F_3 \subseteq \dots \subseteq F_n,$$
where $n \ge 1$ is an integer, each set $F_j$, $1 \le j \le n$, is an essential set, and, for each integer $j \in [1, n-1]$, $F_j$ is positive iff $F_{j+1}$ is negative. The chain $C = (F_j)_{1 \le j \le n}$ is said to be positive (respectively, negative) iff $F_1$ is positive (respectively, negative). The length of the chain $C$ is $n(C) = n$. The maximal length of positive chains of $\mathcal{A}$ is denoted by $m^+(\mathcal{A})$, and the maximal length of negative chains of $\mathcal{A}$ is denoted by $m^-(\mathcal{A})$. The maximal length of chains of $\mathcal{A}$ is $m(\mathcal{A}) = \max(m^+(\mathcal{A}), m^-(\mathcal{A}))$.

An important fact is that the existence of chains, and the integers $m^+(\mathcal{A})$, $m^-(\mathcal{A})$, and $m(\mathcal{A})$, are invariants of the language $L(\mathcal{A})$, meaning that $m^+(\mathcal{A}) = m^+(\mathcal{B})$ and $m^-(\mathcal{A}) = m^-(\mathcal{B})$ hold for any other complete deterministic Muller automaton $\mathcal{B}$ such that $L(\mathcal{A}) = L(\mathcal{B})$.

Wagner also considered the notion of a superchain of an automaton, which provided other invariants of the language of a given automaton. We shall not need this notion in the sequel, so we refer the interested reader to [Wag79] for this. Wagner then defined some classes of languages $C_m^n, D_m^n$ for integers $n, m \ge 1$. We are going to give a definition of the classes $C_m^1$ and $D_m^1$ which can be easily obtained from that given in [Wag79].

**Definition 11** Let $m \ge 1$ be an integer. The classes of regular $\omega$-languages $C_m^1$ and $D_m^1$ are defined by

$$C_m^1 = \{L(\mathcal{A}) \mid m^-(\mathcal{A}) = m \text{ and } m^+(\mathcal{A}) < m\},$$

$$D_m^1 = \{L(\mathcal{A}) \mid m^+(\mathcal{A}) = m \text{ and } m^-(\mathcal{A}) < m\}.$$

**Remark 12** Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, \mathcal{F})$ be a complete deterministic Muller automaton. We can derive from $\mathcal{A}$ the complete deterministic Muller automaton $\mathcal{A}^- = (Q, \Sigma, \delta, q_0, (2^Q \setminus \mathcal{F}))$, and it is easy to see that $L(\mathcal{A}^-) = \Sigma^\omega \setminus L(\mathcal{A})$. Moreover, the automata $\mathcal{A}$ and $\mathcal{A}^-$ have the same essential sets. However, an essential set of $\mathcal{A}$ is positive (respectively, negative) iff it is negative (respectively, positive) for $\mathcal{A}^-$. Thus a positive (respectively, negative) chain of $\mathcal{A}$ is a negative (respectively, positive) chain of $\mathcal{A}^-$. This implies that a regular language $L \subseteq \Sigma^\omega$ is in $C_m^1$ iff its complement $L^-$ is in $D_m^1$.

We now recall an important result proving the existence of a link between the existence of chains of an automaton and the topological complexity of its $\omega$-language.

**Theorem 13 (Wagner [Wag79], Barua [Bar92])** Let $\mathcal{A}$ be a complete deterministic Muller automaton, and $m \ge 2$ be an integer. Then $L(\mathcal{A}) \in C_m^1$ if and only if $L(\mathcal{A})$ is $D_{m-1}(\Pi_2^0)$-complete. Thus $L(\mathcal{A}) \in D_m^1$ if and only if $L(\mathcal{A})$ is $D_{m-1}(\Pi_2^0)$-complete.
This easily follows from a result by Barua in [Bar92]. Barua studied in [Bar92] the Hausdorff-Kuratowski hierarchy of regular $\omega$-languages and proved (using different terminology and notations) that a regular $\omega$-language is in the class $D_n(\Pi_2^0)$ if it is accepted by a complete deterministic Muller automaton $\mathcal{A}$ such that $m^+(\mathcal{A}) \le n$. On the other hand, it follows from the study of the Wadge hierarchy that an $\omega$-language is $D_n(\Pi_2^0)$-complete iff it is in $D_n(\Pi_2^0)$ and not in $D_n^-(\Pi_2^0)$. It is easy to see that an $\omega$-language $L(\mathcal{A})$ is in $C_m^1$ iff $m^-(\mathcal{A}) = m$ and $m^+(\mathcal{A}) = m-1$. Thus $L(\mathcal{A})$ is in $C_m^1$ implies that $L(\mathcal{A})$ is in $D_{m-1}(\Pi_2^0)$, and $L(\mathcal{A})^-$ is not in $D_{m-1}(\Pi_2^0)$ since $m^+(\mathcal{A}^-) = m$. Conversely, it is easy to prove that if $L(\mathcal{A})$ is $D_{m-1}(\Pi_2^0)$-complete then $L(\mathcal{A})$ is in $C_m^1$.

Note that we can recover this from [Wag79, Theorem 14], where an alternative characterization of the hierarchy of differences of $\Pi_2^0$-sets is used. The Hausdorff-Kuratowski hierarchy of regular $\omega$-languages is actually coarser than the Wagner hierarchy.

## 3 Topological complexity of regular $\omega$-powers

We first prove the following result.

**Theorem 14** Let $n$ be a natural number. Then there is a finitary regular language $U_n$ such that $(U_n)^\omega$ is $D_{2n+1}(\Pi_2^0)$-complete.

**Proof.** We first consider the Muller automaton $\mathcal{A}_n = (Q_n, \Sigma, \delta_n, q_1, \mathcal{F}_n)$, where

* $Q_n = \{q_1, q_2, \dots, q_n\}$ (we also set $F_j = \{q_1, q_2, \dots, q_j\}$),

* $\Sigma = \{0, 1\}$,

* $\forall j \in [1, n-1] \ \delta_n(q_j, 1) = q_{j+1}$ and $\forall j \in [1, n] \ \delta_n(q_j, 0) = q_1$,

* $\delta_n(q_n, 1) = q_1$,

* $\mathcal{F}_n = \{F_j \mid 1 \le j \le n \text{ is an even integer}\}$.

It is easy to see that $\mathcal{A}_n$ is a complete deterministic Muller automaton, and that the essential sets of $\mathcal{A}_n$ are exactly the sets $F_j$, $1 \le j \le n$. Thus the maximal chain of $\mathcal{A}_n$ is the negative chain $F_1 \subseteq F_2 \subseteq \dots \subseteq F_n$, $m^-(\mathcal{A}_n) = n$ and $m^+(\mathcal{A}_n) = n-1$. Therefore $L(\mathcal{A}_n) \in C_n^1$ and $L(\mathcal{A}_n)$ is $D_{n-1}(\Pi_2^0)$-complete, for every integer $n \ge 2$.

As an example, we give below the graph of the automaton $\mathcal{A}_4$, for which $\mathcal{F}_4 = \{F_2, F_4\}$.
<figure><img src="image_3.png" /><figcaption>Figure 1: The automaton $\mathcal{A}_4$ for which $\mathcal{F}_4 = \{\{q_1, q_2\}, \{q_1, q_2, q_3, q_4\}\}$.</figcaption></figure>

Note that, for $n = 2$, $L(\mathcal{A}_2) = (0^* \cdot 1)^\omega$ is an $\omega$-power which is known to be $\Pi_2^0$-complete.

However, for $n \ge 3$, $L(\mathcal{A}_n)$ is not an $\omega$-power. Indeed, assume, towards a contradiction, that $L(\mathcal{A}_n) = V^\omega$ for some $V \subseteq \{0, 1\}^+$. We may assume that $V = V^+$. Then, since the $\omega$-word $1010110(10)^\omega$ is accepted by $\mathcal{A}_n$, we could find a finite word $u \in V$ and a natural number $p$ with the properties that $1010110(10)^2 \subseteq u \subseteq 1010110(10)^p$. The infinite word $u^\omega$ would belong to $L(\mathcal{A}_n)$. But it is easy to see that the infinite run $r_{u^\omega}$ of $\mathcal{A}_n$ on $u^\omega$ would satisfy $\mathrm{In}(r_{u^\omega}) = F_3$, and thus the infinite word $u^\omega$ would be rejected by $\mathcal{A}_n$, which is the desired contradiction.

We now assume that $n \ge 3$ is fixed. In order to get some $\omega$-powers of the same complexity as $L(\mathcal{A}_n)$, we first derive another $\omega$-language from the automaton $\mathcal{A}_n$, and this language will be an $\omega$-power. Then we shall look for an Muller automaton accepting this $\omega$-power, which will determine the exact complexity of this $\omega$-power.

We will consider the following language over the alphabet $\Sigma$. We set

$$V_2 = \{u \in \Sigma^+ \mid \delta_n^F(q_1, u) = q_1 \text{ and } F \in \mathcal{F}_n\}.$$

We consider the $\omega$-power $(V_2)^\omega$. We can easily see that $V_2$ is a regular finitary language, and thus the $\omega$-power $(V_2)^\omega$ is a regular $\omega$-language accepted by a deterministic complete Muller automaton.

We now state the following lemma.

**Lemma 15** (1) It holds that $(V_2)^\omega \subseteq L(\mathcal{A}_n)$. (2) an $\omega$-word $x$ accepted by the automaton $\mathcal{A}_n$ belongs to the set $(V_2)^\omega$ if the run $r$ of $\mathcal{A}_n$ on $x$ satisfies $\mathrm{In}(r) = F_k$ for some even integer $k \in [1, n]$ and

$$\max\{j \in [1, n] \mid \mathcal{A}_n \text{ enters in the state } q_j \text{ during the run } r\}$$

is an even integer.
**Proof.** (1) Let $x = u_1u_2\dots u_k\dots$ be an infinite word where for each integer $k \ge 1$ it holds that $u_k \in V_2$. Then, for each $k \ge 1$, $\delta_n^{F_{ik}}(q_1, u_k) = q_1$ for some even integer $i_k \in [1, n]$. Now if $I$ is the maximum of the integers $j \in [1, n]$ for which there are infinitely many integers $k$ such that $i_k = j$ then it is clear that the run $r$ of $A_n$ on $x$ will satisfy $\text{In}(r) = F_I$. Moreover, the integer $I$ is even and thus we have $x \in L(A_n)$.

(2) From the above proof of Item (1), we can infer that if $x = u_1u_2\dots u_k\dots$ is an infinite word where, for each integer $k \ge 1$, $u_k \in V_2$, and if $r$ is the run of $A_n$ on $x$ then

$$ \max\{j \in [1, n] \mid A_n \text{ enters in the state } q_j \text{ during the run } r\} $$

is the maximum of the finite set of even integers $\{i_k \in [1, n] \mid k \ge 1\}$ which is also an even integer.

Conversely, assume that an $\omega$-word $x$ is accepted by the automaton $A_n$, that the run of $A_n$ on $x$ satisfies $\text{In}(r) = F_k$ for some even integer $k \in [1, n]$ and

$$ \max\{j \in [1, n] \mid A_n \text{ enters in the state } q_j \text{ during the run } r\} $$

is an even integer $M$. Then it is easy to see that the infinite word $x$ can be decomposed as $x = u_1u_2\dots u_j\dots$, where the $u_j, j \ge 1$, are finite words such that $\delta_n^{F_M}(q_1, u_1) = q_1$ and $\delta_n^{F_k}(q_1, u_j) = q_1$ for every $j \ge 2$. This implies that $x \in (V_2)^\omega$. $\square$

We now construct a Muller automaton $C = (T_n, \Sigma, \delta'_n, q_0, \mathcal{F}'_n)$ accepting the $\omega$-power $(V_2)^\omega$.

The set of states of $C$ is $T_n = \{q_0\} \cup \{(q_j, k) \mid q_j \in Q_n \text{ and } k \in [1, n]\}$. The automaton $C$ will then simply simulate the automaton $A_n$ in the first component of its states, and will store the maximum of the integers $j$ such that the simulation of $A_n$ has already entered in the state $q_j$ in the second component of its states.

The first transition of $C$ starts from state $q_0$ and simulates the first transition of $A_n$ as it starts from $q_1$; thus $\delta'_n(q_0, 0) = (q_1, 1)$ holds, as well as $\delta'_n(q_0, 1) = (q_2, 2)$. Then, for each letter $a \in \{0, 1\}$, the transition $\delta'_n((q_j, k), a) = (q_{k'}, \sup(k, k'))$ exists, where $\delta_n(q_j, a) = q_{k'}$. Note that, during an infinite run of $C$, the second component of the visited states will stabilize at some integer $k$. Thus we can define $F \in \mathcal{F}'_n$ iff $F = \{(q_1, k), (q_2, k), \dots, (q_{2i}, k)\}$ for some even integer $k$ such that $2i \le k$.

We have constructed the complete deterministic Muller automaton $C$. Now, in order to determine the topological complexity of the $\omega$-language $(V_2)^\omega$, we look at the length of chains in the automaton $C$.
We set $F_j^k = \{(q_1, k), (q_2, k), \dots, (q_j, k)\}$ for $j \le k$. Then, in the automaton $C$, the maximal chain is $F_1^k \subseteq F_2^k \subseteq \dots \subseteq F_k^k$, where $k$ is the largest even integer $\le n$. This chain is negative since $F_1^k$ is a negative essential set. And if $n$ is even, then this chain has length $n$, while it has length $n-1$ if $n$ is odd.

Summarizing, if $n = 2p$ is even, then $m^-(C) = 2p$ and $m^+(C) = 2p-1$, thus $L(C) \in C_{2p}^1$. By Theorem 13, $L(C)$ is $D_{2p-1}(\Pi_2^0)$-complete. This finishes the proof of Theorem 14.

Note that if $n = 2p+1$ is odd, then $m^-(C) = 2p$ and $m^+(C) = 2p-1$, so that $L(C) \in C_{2p}^1$ and $L(C)$ is also $D_{2p-1}(\Pi_2^0)$-complete. $\square$

We now prove the following result.

**Theorem 16** Let $n$ be a natural number. Then there is a finitary regular language $V_n$ such that $(V_n)^\omega$ is $D_{2n+2}^-(\Pi_2^0)$-complete.

**Proof.** We use a reasoning similar to that in the proof of the preceding theorem. We first consider the Muller automaton

$$A_n^- = (Q_n, \Sigma, \delta_n, q_1, 2^{Q_n} \setminus F_n = F_n^-),$$

where

* $Q_n = \{q_1, q_2, \dots, q_n\}$ (we also set $F_j = \{q_1, q_2, \dots, q_j\}$),

* $\Sigma = \{0, 1\}$,

* $\forall j \in [1, n-1] \ \delta_n(q_j, 1) = q_{j+1}$ and $\forall j \in [1, n] \ \delta_n(q_j, 0) = q_1$,

* $\delta_n(q_n, 1) = q_1$,

* $F_n^- \cap M(A_n^-) = \{F_j \mid j \le n \text{ is an odd integer}\}$, so in the sequel we shall denote, without loss of generality, $F_n^- = \{F_j \mid j \le n \text{ is an odd integer}\}$.

The automaton $A_n^-$ is a complete deterministic Muller automaton. Note that $m^+(A_n^-) = n$ and $m^-(A_n^-) = n-1$. For every integer $n \ge 2$, $L(A_n)$ is in $C_n^1$ and thus $L(A_n^-) = L(A_n)^- \in D_n^1$. Moreover, $L(A_n^-)$ is $D_{n-1}^-(\Pi_2^0)$-complete.

We now consider, following the scheme of the proof of Theorem 14, the language, over the alphabet $\Sigma$, defined by:

$$V_2' = \{u \in \Sigma^+ \mid \delta_n^F(q_1, u) = q_1 \text{ and } F \in \mathcal{F}_n^-\}.$$

We now consider the $\omega$-power $(V_2')^\omega$, and also construct an automaton $C' = (T_n, \Sigma, \delta'_n, q_0, \mathcal{F}_n'')$ accepting the $\omega$-language $(V_2')^\omega$.

We first state the following lemma.
**Lemma 17** (1) It holds that $(V'_2)^\omega \subseteq L(\mathcal{A}_n^-)$. (2) an $\omega$-word $x$ accepted by the automaton $\mathcal{A}_n^-$ belongs to the set $(V'_2)^\omega$ if the run $r$ of $\mathcal{A}_n^-$ on $x$ satisfies $\text{In}(r) = F_k$ for some odd integer $k \in [1, n]$ and

$$ \max\{j \in [1, n] \mid \mathcal{A}_n^- \text{ enters in the state } q_j \text{ during the run } r\} $$

is an odd integer.

**Proof.** It is very similar to the proof of Lemma 15. Details are here left to the reader. $\square$

The set of states $T_n$ of $C'$ is the same as that of the automaton $C$. The automaton $C'$ will then simply simulate the automaton $\mathcal{A}_n^-$ in the first component of its states, and will store the maximum of the integers $j$ such that the simulation of $\mathcal{A}_n^-$ has already entered in the state $q_j$ in the second component of its states.

The first transition of $C'$ starts from the state $q_0$ and simulates the first transition of $\mathcal{A}_n^-$ as it starts from $q_1$; thus $\delta'_n(q_0, 0) = (q_1, 1)$ and $\delta'_n(q_0, 1) = (q_2, 2)$. Then we have, for each letter $a \in \{0, 1\}$, the transition $\delta'_n((q_j, k), a)) = (q_{k'}, \sup(k, k'))$ where $\delta_n(q_j, a) = q_{k'}$. Note that, during an infinite run of $C'$, the second component of the visited states will stabilize at some integer $k$. Thus we can define $F \in \mathcal{F}_n''$ if and only if $F = \{(q_1, k), (q_2, k), \dots, (q_{2i+1}, k)\}$, for some odd integers $k$ and $2i+1 \le k$.

Now, in order to determine the topological complexity of the $\omega$-language $(V'_2)^\omega$, we look at the length of chains in the automaton $C'$.

We set $F_j^k = \{(q_1, k), (q_2, k), \dots, (q_j, k)\}$ for $j \le k$. Then, in the automaton $C'$, the maximal chain is $F_1^k \subseteq F_2^k \subseteq \dots \subseteq F_k^k$, where $k$ is the largest odd integer $\le n$. This chain is positive since $F_1^k$ is a positive essential set. And if $n$ is odd, then this chain has length $n$, while it has length $n-1$ if $n$ is even.

Summarizing, if $n = 2p+1$ is odd, then $m^-(C') = 2p$ and $m^+(C') = 2p+1$, so that $L(C') \in D_{2p+1}^1$ and, by Theorem 13, $L(C')$ is $D_{2p}^- (\Pi_2^0)$-complete. This finishes the proof of Theorem 16.

Note that if $n = 2p+2$ is even, then $m^-(C') = 2p$ and $m^+(C') = 2p+1$, thus $L(C') \in D_{2p+1}^1$, and $L(C')$ is also $D_{2p}^- (\Pi_2^0)$-complete. $\square$

# 4 Concluding remarks

We have proved that, for each natural number $n$, there are finitary regular languages $U_n$ and $V_n$ such that $(U_n)^\omega$ is $D_{2n+1}(\Pi_2^0)$-complete and $(V_n)^\omega$ is $D_{2n+2}^-(\Pi_2^0)$-complete. It remains open whether there are some (regular) $\omega$-powers which are $D_{2n+2}(\Pi_2^0)$-complete and $D_{2n+1}^-(\Pi_2^0)$-complete.
On the other hand, the hierarchy of the finite differences of $\Pi_2^0$-sets in a Cantor space $X^\omega$ can be extended to transfinite countable ordinal ranks, and it is known that $\Delta_3^0 = \bigcup_{\alpha<\omega_1} D_\alpha(\Pi_2^0)$. An open question is whether there are some $\Delta_3^0$ $\omega$-powers of infinite rank in this hierarchy, which could not be regular if they exist.

Note that we in particular proved that the Wadge hierarchy of $\omega$-powers of regular languages is infinite and has at least length $\omega$. On the other hand, O. Finkel and D. Lecomte recently proved in [FL24] that, for each natural number $n$, there are some regular finitary languages $W_n$ and $W_n'$ such that the $\omega$-power $W_n^\omega$ (respectively, $W_n'^\omega$) is $D_n(\Sigma_1^0)$-complete (respectively, $D_n^-(\Sigma_1^0)$-complete). This shows that the length of the Wadge hierarchy of $\omega$-powers of regular languages is actually greater than or equal to $\omega + \omega$.

For future study, it remains to completely determine the Wadge hierarchy of (regular or non-regular) $\omega$-powers.

## References

[Bar92] R. Barua. The Hausdorff-Kuratowski hierarchy of omega-regular languages and a hierarchy of Muller automata. *Theoretical Computer Science*, 96(2):345-360, 1992.

[DF07] J. Duparc and O. Finkel. An $\omega$-power of a context free language which is Borel above $\Delta_\omega^0$. In *Proceedings of the International Conference Foundations of the Formal Sciences V : Infinite Games, November 26th to 29th, 2004, Bonn, Germany*, volume 11 of College Publications at King's College (Studies in Logic), pages 109-122, 2007.

[Dup01] J. Duparc. Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank. *Journal of Symbolic Logic*, 66(1):56-86, 2001.

[Fin01] O. Finkel. Topological properties of omega context free languages. *Theoretical Computer Science*, 262(1-2):669-697, 2001.

[Fin03] O. Finkel. Borel hierarchy and omega context free languages. *Theoretical Computer Science*, 290(3):1385-1405, 2003.

[Fin04] O. Finkel. An $\omega$-power of a finitary language which is a Borel set of infinite rank. *Fundamenta Informaticae*, 62(3-4):333-342, 2004.

[FL07] O. Finkel and D. Lecomte. There exist some $\omega$-powers of any Borel rank. In *Proceedings of the 16th EACSL Annual International Conference on Computer Science and Logic, CSL 2007, Lausanne, Switzerland, September 11-15, 2007*, volume 4646 of Lecture Notes in Computer Science, pages 115-129. Springer, 2007.
[FL09] O. Finkel and D. Lecomte. Classical and effective descriptive complexities of $\omega$-powers. *Annals of Pure and Applied Logic*, 160(2):163-191, 2009.

[FL20] O. Finkel and D. Lecomte. Descriptive set theory and $\omega$-powers of finitary languages. In *Contemporary Logic and Computing*, volume 1 of *Landscapes in Logic*, pages 518-541. College Publications, London, 2020.

[FL21] O. Finkel and D. Lecomte. Some complete $\omega$-powers of a one-counter language, for any borel class of finite rank. *Archive for Mathematical Logic*, 60(1-2):161-187, 2021.

[FL24] O. Finkel and D. Lecomte. Wadge degrees of $\Delta_2^0$ omega-powers. *Mathematical Logic Quarterly*, 70(3):286-293, 2024.

[Kec95] A. S. Kechris. *Classical descriptive set theory*. Springer-Verlag, New York, 1995.

[Lan69] L.H. Landweber. Decision problems for $\omega$-automata. *Mathematical Systems Theory*, 3(4):376-384, 1969.

[Lec05] D. Lecomte. $\omega$-powers and descriptive set theory. *Journal of Symbolic Logic*, 70(4):1210-1232, 2005.

[LT87] I. Litovsky and E. Timmerman. On generators of rational omega-power languages. *Theoretical Computer Science*, 53:187-200, 1987.

[Niw90] D. Niwinski. A problem on $\omega$-powers. In *1990 Workshop on Logics and Recognizable Sets*, University of Kiel, 1990.

[PP04] D. Perrin and J.-E. Pin. *Infinite words, automata, semigroups, logic and games*, volume 141 of *Pure and Applied Mathematics*. Elsevier, 2004.

[Sel98] V.L. Selivanov. Fine hierarchy of regular $\omega$-languages. In *Theoretical Computer Science*, 191:37-59, 1998.

[Sel08a] V.L. Selivanov. Fine hierarchies and m-reducibilities in theoretical computer science. *Theoretical Computer Science*, 405(1-2):116-163, 2008.

[Sel08b] V.L. Selivanov. Wadge reducibility and infinite computations. *Special Issue on Intensional Programming and Semantics in honour of Bill Wadge on the occasion of his 60th cycle, Mathematics in Computer Science*, 2(1):5-36, 2008.

[Sim92] P. Simonnet. *Automates et théorie descriptive*. PhD thesis, Université Paris VII, 1992.
[Sta97a] L. Staiger. ω-languages. In *Handbook of formal languages*, Vol. 3, pages 339–387. Springer, Berlin, 1997.

[Sta97b] L. Staiger. On ω-power languages. In *New Trends in Formal Languages, Control, Cooperation, and Combinatorics*, volume 1218 of *Lecture Notes in Computer Science*, pages 377–393. Springer-Verlag, Berlin, 1997.

[Tho90] W. Thomas. Automata on infinite objects. In J. van Leeuwen, editor, *Handbook of Theoretical Computer Science*, volume B, Formal models and semantics, pages 135–191. Elsevier, 1990.

[Wad83] W. Wadge. *Reducibility and determinateness in the Baire space*. PhD thesis, University of California, Berkeley, 1983.

[Wag79] K. Wagner. On ω-regular sets. *Information and Control*, 43(2):123–177, 1979.