# Topologies Refining the Cantor Topology on Xω

Sibylle Schwarz, Ludwig Staiger

► To cite this version:

Sibylle Schwarz, Ludwig Staiger. Topologies Refining the Cantor Topology on Xω. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. pp.271-285, 10.1007/978-3-642-15240-5_20. hal-01054453

HAL Id: hal-01054453

https://inria.hal.science/hal-01054453

Submitted on 6 Aug 2014

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Topologies refining the Cantor topology on $X^ω$

Sibylle Schwarz¹ and Ludwig Staiger²

¹ Fachgruppe Informatik, Westsächsische Hochschule Zwickau
sibylle.schwarz@fh-zwickau.de

² Institut für Informatik, Martin-Luther-Universität Halle-Wittenberg
staiger@informatik.uni-halle.de

**Abstract** The space of one-sided infinite words plays a crucial rôle in several parts of Theoretical Computer Science. Usually, it is convenient to regard this space as a metric space, the Cantor-space. It turned out that for several purposes topologies other than the one of the Cantor-space are useful, e.g. for studying fragments of first-order logic over infinite words or for a topological characterisation of random infinite words.

It is shown that both of these topologies refine the topology of the Cantor-space. Moreover, from common features of these topologies we extract properties which characterise a large class of topologies. It turns out that, for this general class of topologies, the corresponding closure and interior operators respect the shift operations and also, to some respect, the definability of sets of infinite words by finite automata.

The space of one-sided infinite words plays a crucial rôle in several parts of Theoretical Computer Science (see [7,20] and the surveys [6,13,17,18]). Usually, it is convenient to regard this space as a topological space provided with the CANTOR topology. This topology can be also considered as the natural continuation of the left topology of the prefix relation on the space of finite words; for a survey see [2].

It turned out that for several purposes other topologies on the space of infinite words are also useful [9,12], e.g. for investigations in first-order logic [3], to characterise the set of random infinite words [1] or the set of disjunctive infinite words [15] and to describe the converging behaviour of not necessarily hyperbolic iterative function systems [5,14].

Most of these papers use topologies on the space of infinite words which are certain refinements of the CANTOR topology showing a certain kind of shift invariance. The aim of this paper is to give a unified treatment of those topologies and to investigate their relations to CANTOR topology.

Special attention is paid to subsets of the space of infinite words definable by finite automata. It turns out that several of the refinements of the CANTOR topology under consideration behave well with respect to finite automata, that is, the corresponding closure and interior operators preserve at least one of the classes of finite-state or regular $ω$-languages.
# 1 Notation and Preliminaries

We introduce the notation used throughout the paper. By $\mathbb{N} = \{0, 1, 2, \dots\}$ we denote the set of natural numbers. Let $X$ be a finite alphabet of cardinality $|X| = r \ge 2$. By $X^*$ we denote the set (monoid) of words on $X$, including the empty word $e$, and $X^\omega$ is the set of infinite sequences ($\omega$-words) over $X$. For $w \in X^*$ and $\eta \in X^* \cup X^\omega$ let $w \cdot \eta$ be their concatenation. This concatenation product extends in an obvious way to subsets $W \subseteq X^*$ and $P \subseteq X^* \cup X^\omega$. For a language $W$ let $W^* := \bigcup_{i \in \mathbb{N}} W^i$ be the submonoid of $X^*$ generated by $W$, and by $W^\omega := \{w_1 \cdots w_i \cdots : w_i \in W \setminus \{e\}\}$ we denote the set of infinite strings formed by concatenating words in $W$. Furthermore $|w|$ is the length of the word $w \in X^*$ and **pref**($P$) is the set of all finite prefixes of strings in $P \subseteq X^* \cup X^\omega$. We shall abbreviate $w \in \mathbf{pref}(\eta)$ ($\eta \in X^* \cup X^\omega$) by $w \sqsubseteq \eta$. A language $V \subseteq X^*$ is called a *prefix-free* provided for arbitrary $w, v \in V$ the relation $w \sqsubseteq v$ implies $w = v$.

Further we denote by $P/w := \{\eta : w \cdot \eta \in P\}$ the left derivative or state of the set $P \subseteq X^* \cup X^\omega$ generated by the word $w$. We refer to $P$ as finite-state provided the set of states $\{P/w : w \in X^*\}$ is finite. It is well-known that a language $W \subseteq X^*$ is finite state if and only if it is accepted by a finite automaton, that is, it is a regular language.<fnref n="1" />

In the case of $\omega$-languages *regular* $\omega$-languages, that is, $\omega$-languages accepted by finite automata, are the finite unions of sets of the form $W \cdot V^\omega$, where $W$ and $V$ are regular languages (cf. e.g. [13]). In particular, every regular $\omega$-language is finite-state, but, as it was observed in [19], not every finite-state $\omega$-language is regular (cf. also [11]).

It is well-known that the families of regular or finite-state $\omega$-languages are closed under Boolean operations [7,20,6,13,17,18] or [11].

## 1.1 Topological Spaces in General

A topological space is a pair $(\mathcal{X}, \mathcal{O})$ where $\mathcal{X}$ is a non-empty set and $\mathcal{O} \subseteq 2^{\mathcal{X}}$ is a family of subsets of $\mathcal{X}$ which is closed under arbitrary union and under finite intersection. The family $\mathcal{O}$ is usually called the family of *open* subsets of the space $\mathcal{X}$. Their complements are referred to as *closed* sets of the space $\mathcal{X}$.

As usually, a set $\mathbb{B} \subseteq \mathcal{O}$ is a *base* for a topology $(\mathcal{X}, \mathcal{O})$ on $\mathcal{X}$ provided every set $M \in \mathcal{O}$ is the (possibly empty) union of sets from $\mathbb{B}$. Thus it does no harm if one considers bases containing $\emptyset$. It is well-known that a family of subsets $\mathbb{B}$ of a set $\mathcal{T}$ which is closed under finite intersection generates in this way a topology on $\mathcal{T}$.

Kuratowski observed that topological spaces can be likewise defined using closure or interior operators. A topological *interior* operator $\mathcal{J}$ is a mapping $\mathcal{J} : 2^{\mathcal{X}} \to 2^{\mathcal{X}}$ satisfying the following relations. It assigns to a subset $M \subseteq \mathcal{X}$

<footnote n="1">¹ Observe that the relation $\sim_P$ defined by $w \sim_P v$ iff $P/w = P/v$ is the NERODE right congruence of $P$.</footnote>
the largest open set contained in $M$.

$$ \begin{aligned} \mathcal{J}\mathcal{X} &= \mathcal{X} \\ \mathcal{J}\mathcal{J}M &= \mathcal{J}M \subseteq M, \text{ and} \\ \mathcal{J}(M_1 \cap M_2) &= \mathcal{J}M_1 \cap \mathcal{J}M_2 \end{aligned} \tag{1} $$

The interior operator $\mathcal{J}$ mapping each subset $M \subseteq \mathcal{X}$ to the largest open set contained in $M$ can be described as follows.

$$ \mathcal{J}(M) := \bigcup \{B : B \subseteq M \wedge B \in \mathbb{B}\} \tag{2} $$

Using the complementary (duality) relation between open and closed sets one defines the closure (smallest closed set containing) of $M$ as follows.

$$ \mathcal{C}M := \mathcal{X} \setminus \mathcal{J}(\mathcal{X} \setminus M) \tag{3} $$

Then the following holds.

$$ \begin{aligned} \mathcal{C}\emptyset &= \emptyset \\ \mathcal{C}CM &= CM \supseteq M \\ \mathcal{C}(M_1 \cup M_2) &= CM_1 \cup CM_2 \end{aligned} \tag{4} $$

As usual, in a topological space, we denote the classes of countable unions of closed sets as $\mathbf{F}_\sigma$ and of countable intersections of open sets as $\mathbf{G}_\delta$.

## 1.2 The Cantor-space: basic properties

In this section we list some properties of the Cantor-space (see [7,13,17,20]).

We consider the space of infinite words ($\omega$-words) $X^\omega$ as a metric space with metric $\rho$ defined as follows

$$ \rho(\xi, \eta) := \begin{cases} 0, & \text{if } \xi = \eta, \text{ and} \\ \sup\{|X|^{-|w|} : w \in \mathbf{pref}(\xi) \cap \mathbf{pref}(\eta)\} & \text{if } \xi \neq \eta. \end{cases} \tag{5} $$

This space $(X^\omega, \rho)$ can be also considered as a topological space with base $\mathbb{B}_C := \{w \cdot X^\omega : w \in X^*\} \cup \{\emptyset\}$.2
Then the following is well-known.

Property 1. 1. Open sets in Cantor-space $(X^\omega, \rho)$ are of the form $W \cdot X^\omega$ where $W \subseteq X^*$.

2. A subset $E \subseteq X^\omega$ is open and closed (clopen) if and only if $E = W \cdot X^\omega$ where $W \subseteq X^*$ is finite.

3. A subset $F \subseteq X^\omega$ is closed if and only if $F = \{\xi : \mathbf{pref}(\xi) \subseteq \mathbf{pref}(F)\}$.

4. $C(F) := \{\xi : \xi \in X^\omega \wedge \mathbf{pref}(\xi) \subseteq \mathbf{pref}(F)\} = \bigcap_{n \in \mathbb{N}} (\mathbf{pref}(F) \cap X^n) \cdot X^\omega$ is the closure of $F$.

<footnote n="2">2 It is sometimes convenient to include the empty set into a base. Here $\mathbb{B}_C$ becomes a Boolean algebra.</footnote>
5. If $F$ is a finite-state $\omega$-language then $C(F)$ and $J(F)$ are regular $\omega$-languages.

Moreover, the CANTOR-space $(X^\omega, \rho)$ is a compact space, that is, for every family of open sets $(E_i)_{i \in I}$ such that $\bigcup_{i \in I} E_i = X^\omega$ there is a finite sub-family $(E_i)_{i \in I'}$ satisfying $\bigcup_{i \in I'} E_i = X^\omega$. This property is in some sense characteristic for the CANTOR topology on $X^\omega$. In particular, no topology refining CANTOR topology and having at least one isolated point<fnref n="3" /> is compact.

**Lemma 1.** Let $(X^\omega, \mathcal{O})$ be a topology such that $\{W \cdot X^\omega : W \subseteq X^*\} \subseteq \mathcal{O}$ and there is a $\xi \in X^\omega$ satisfying $\{\xi\} \in \mathcal{O}$. Then the space $(X^\omega, \mathcal{O})$ is not compact.

*Proof.* It suffices to give an infinite family $(E_i)_{i \in \mathbb{N}}$ of pairwise disjoint open sets with $\bigcup_{i \in \mathbb{N}} E_i = X^\omega$.

Let $\mathcal{U} := (\mathbf{pref}(\xi) \cdot X) \setminus \mathbf{pref}(\xi)$. Then the sets $w \cdot X^\omega, w \in \mathcal{U}$, are pairwise disjoint and satisfy $\xi \notin w \cdot X^\omega$. It is now easy to see that $X^\omega = \{\xi\} \cup \bigcup_{w \in \mathcal{U}} w \cdot X^\omega$.

## 1.3 Regular $\omega$-languages

As a last part of this section we mention some facts on regular $\omega$-languages known from the literature, e.g. [7,13,17,20].

The first one shows the importance of ultimately periodic $\omega$-words. Denote by $\text{Ult} := \{w \cdot v^\omega : w, v \in X^* \setminus \{e\}\}$ the set of ultimately periodic $\omega$-words.

**Lemma 2 (Büchi).** The class of regular $\omega$-languages is a Boolean algebra.

Every non-empty regular $\omega$-language contains an ultimately periodic $\omega$-word, and regular $\omega$-languages $E, F \subseteq X^\omega$ coincide if only $E \cap \text{Ult} = F \cap \text{Ult}$.

The next one gives a connection between accepting devices and topology.

**Theorem 1 (Landweber).** An $\omega$-language $F$ is accepted by a deterministic BÜCHI automaton if and only if $F$ is regular and a $G_\delta$-set.

And, finally, we obtain a topological sufficient condition when finite-state $\omega$-languages are regular.

**Theorem 2 ([11]).** Every finite-state $\omega$-language in the class $F_\sigma \cap G_\delta$ is already regular.

# 2 Topologies Refining the CANTOR Topology

In this section we consider some general principles pursued in this paper of the refinement of the CANTOR topology. Most of the following topologies are defined by introducing a suitable base for the topology. In the sequel, we will often require that our bases $\mathbb{B} \subseteq 2^{X^\omega}$ in the space $X^\omega$ satisfy the following condition.

**Definition 1.** We will refer to a base $\mathbb{B}$ for a topology $\mathcal{T}$ on $X^\omega$ as shift-invariant provided

$$ \forall F \forall w \forall v (F \in \mathbb{B} \land w \in X^* \land v \in \mathbf{pref}(F) \rightarrow w \cdot F, F/v \in \mathbb{B}). \quad (6) $$

<footnote n="3">³ A point $\xi \in X^\omega$ is called isolated if $\{\xi\}$ is an open set.</footnote>
The property in Definition 1 is, in particular, satisfied for the base $\mathbb{B}_C$. It is now easy to see that for shift-invariant bases the following holds true.

Topologies on the space of finite words satisfying the same condition as in Eq. (6) were investigated in [8].

**Property 2.** 1. If $\mathbb{B}$ is a shift invariant base for a topology on $X^\omega$ then $\forall w(w \in X^* \to \forall E(E \in \mathbb{B} \leftrightarrow w \cdot E \in \mathbb{B}))$.

2. If $\mathbb{B}$ is a base for a topology on $X^\omega$ satisfying $X^\omega \in \mathbb{B}$ and $\forall w(w \in X^* \to \forall E(E \in \mathbb{B} \leftrightarrow w \cdot E \in \mathbb{B}))$ then $\mathbb{B}$ is shift-invariant.

3. A topology $\mathcal{T}$ on $X^\omega$ has a shift-invariant base if and only if $\forall w(w \in X^* \to \forall E(E$ is open in $\mathcal{T} \leftrightarrow w \cdot E$ is open in $\mathcal{T}))$.

The proof of Property 2.3 uses the obvious fact that the set of all open sets is itself a base for the topology.

Moreover, Property 2.3 shows that all topologies on $X^\omega$ having a shift-invariant base refine the CANTOR topology. The converse is not true as we shall see in Section 4.3.

Next we are going to describe the interior operator in topologies on $X^\omega$ having a shift-invariant base. To this end we call a subset $M_{\mathbb{B}} \subseteq \mathbb{B}$ of a base a *shift generator* of $\mathbb{B}$ provided $\mathbb{B} \setminus \{\emptyset\} \subseteq \{w \cdot E : w \in X^* \wedge E \in M_{\mathbb{B}}\}$. In particular, if $\mathbb{B}$ is shift invariant, $\mathbb{B}$ itself and $\mathbb{B} \setminus \{\emptyset\}$ are shift generators of $\mathbb{B}$. For the CANTOR topology, for instance, $M_{\mathbb{B}_C} = \{X^\omega\}$ is a minimal shift generator of $\mathbb{B}_C$.

Now, the interior operator can be described using a suitably chosen shift generator $M_{\mathbb{B}}$ and the following construction. Let $E, F \subseteq X^\omega$. We set

$$L(F; E) := \{w : w \in X^* \wedge F/w \supseteq E\}. \qquad (7)$$

**Lemma 3.** Let $\mathbb{B}$ be a shift-invariant base, and let $M_{\mathbb{B}} \subseteq \mathbb{B}$ be a shift generator of $\mathbb{B}$. If $\mathcal{J}$ is the corresponding interior operator then

$$\mathcal{J}(F) = \bigcup_{E \in M_{\mathbb{B}}} L(F; E) \cdot E$$

for every $F \subseteq X^\omega$.

*Proof.* Since $\mathcal{J}(F)$ is open, it is a union of base sets. In view of the special property of our base there are a family of sets $E_j \in M_j$ and a family of words $w_j \in X^*$ such that $\mathcal{J}(F) = \bigcup_{j \in J} w_j \cdot E_j$. Thus $F/w_j \supseteq E_j$ for $j \in J$, that is, $w_j \in L(F; E_j)$. Now, the assertion follows with $\bigcup_{j \in J} w_j \cdot E_j = \bigcup_{j \in J} L(F; E_j) \cdot E_j$.

It should be mentioned that the languages $L(F; E)$ have a simple structure, if only $F$ has a simple structure.

**Lemma 4.** If $F \subseteq X^\omega$ is finite-state then $L(F; E)$ is a regular language.

*Proof.* It suffices to prove the identity

$$L(F/v; E) = L(F; E)/v. \qquad (8)$$

Indeed, we have $w \in L(F/v; E)$ if and only if $F/(v \cdot w) \supseteq E$ which, in turn, is equivalent to $v \cdot w \in L(F; E)$, that is, $w \in L(F; E)/v$.
The subsequent lemma shows that for shift-invariant topologies on $X^\omega$ the closure and the interior operator are stable with respect to the derivative.

**Lemma 5.** If $\mathbb{B}$ is a shift-invariant base then $\mathcal{J}_{\mathbb{B}}(F)/v = \mathcal{J}_{\mathbb{B}}(F/v)$ and $\mathcal{C}_{\mathbb{B}}(F)/v = \mathcal{C}_{\mathbb{B}}(F/v)$ for all $F \subseteq X^\omega$ and $v \in X^*$.

*Proof.* Let $M_{\mathbb{B}}$ be a shift generator for $\mathbb{B}$. Then, in view of Eq. (8),

$$ \begin{aligned} \mathcal{J}_{\mathbb{B}}(F)/v &= \left( \bigcup_{E \in M_{\mathbb{B}}} L(F; E) \cdot E \right)/v \\ &= \bigcup_{E \in M_{\mathbb{B}}} \left( L(F; E)/v \right) \cdot E \cup \bigcup_{E \in M_{\mathbb{B}}} \bigcup_{\substack{v' \cdot v'' = v \\ v' \in L(F; E)}} E/v'' . \end{aligned} $$

Thus it remains to show that $E'/v'' \subseteq \bigcup_{E \in M_{\mathbb{B}}} (L(F; E)/v) \cdot E$ whenever $E' \in M_{\mathbb{B}}$ and $v = v' \cdot v''$ with $v' \in L(F; E)$. In the case the latter conditions are satisfied we have $F/v' \supseteq E'$ which implies $F/v \supseteq E'/v''$.

In view of Eq. (6) $E'/v'' \in \mathbb{B}$ for $E' \in \mathbb{B}$. Consequently, there are $u \in X^*$ and an $E'' \in M_{\mathbb{B}}$ such that $E'/v'' = u \cdot E''$. From $F/v \supseteq E'/v'' = u \cdot E''$ follows $(F/v)/u \supseteq E''$, that is, $u \in L(F/v; E'') = L(F; E'')/v$. The proof is concluded by the now obvious observation $E'/v'' = u \cdot E'' \subseteq (L(F; E'')/v) \cdot E''$.

The proof for $\mathcal{C}_{\mathbb{B}}$ follows from the identity $X^\omega \setminus E/w = (X^\omega \setminus E)/w$ and Eq. (3).

As a consequence of Lemma 5 we obtain

**Corollary 1.** If $\mathbb{B}$ is a shift-invariant base for a topology on $X^\omega$ then $\mathcal{J}_{\mathbb{B}}(v \cdot F) = v \cdot \mathcal{J}_{\mathbb{B}}(F)$ and $\mathcal{C}_{\mathbb{B}}(v \cdot F) = v \cdot \mathcal{C}_{\mathbb{B}}(F)$ for all $F \subseteq X^\omega$ and $v \in X^*$.

*Proof.* First observe that in view of Property 2.3 the topology $\mathcal{I}_{\mathbb{B}}$ generated by the shift-invariant base $\mathbb{B}$ refines the CANTOR topology on $X^\omega$, hence every set $v \cdot X^\omega$ is also open and closed in $\mathcal{I}_{\mathbb{B}}$. Consequently, $\mathcal{J}_{\mathbb{B}}(v \cdot F) \subseteq \mathcal{C}_{\mathbb{B}}(v \cdot F) \subseteq v \cdot X^\omega$.

Now according to Lemma 5 the identities $\mathcal{J}_{\mathbb{B}}(F) = \mathcal{J}_{\mathbb{B}}((v \cdot F)/v) = \mathcal{J}_{\mathbb{B}}(v \cdot F)/v$ hold. This yields $v \cdot \mathcal{J}_{\mathbb{B}}(F) = \mathcal{J}_{\mathbb{B}}(v \cdot F) \cap v \cdot X^\omega$ and the assertion follows with $\mathcal{J}_{\mathbb{B}}(v \cdot F) \subseteq v \cdot X^\omega$. The proof for $\mathcal{C}_{\mathbb{B}}$ is the same.

The following is a consequence of the Lemmata 3, 4 and 5.

**Corollary 2.** Let a base $\mathbb{B}$ for a topology on $X^\omega$ be shift-invariant and let $F \subseteq X^\omega$ be a finite-state $\omega$-language.

1. Then $\mathcal{J}_{\mathbb{B}}(F)$ and $\mathcal{C}_{\mathbb{B}}(F)$ are finite-state $\omega$-languages.

2. If moreover, there is a finite shift generator $M_{\mathbb{B}}$ of $\mathbb{B}$ consisting solely of regular $\omega$-languages then $\mathcal{J}_{\mathbb{B}}(F)$ and $\mathcal{C}_{\mathbb{B}}(F)$ are even regular $\omega$-languages.

*Proof.* The classes of finite-state and regular $\omega$-languages are both closed under Boolean operations. Thus the first assertion follows from Lemma 5.

For proving the assertion on the regularity of the $\omega$-languages $\mathcal{J}_{\mathbb{B}}(F)$ and $\mathcal{C}_{\mathbb{B}}(F)$ we observe that the strong assumption on $M_{\mathbb{B}}$ and Lemmata 3 and 4 yield $\mathcal{J}_{\mathbb{B}}(F) = \bigcup_{E \in M_{\mathbb{B}}} L(F; E) \cdot E$ where the union is finite and $L(F; E) \subseteq X^*$ and $E \subseteq X^\omega$ are regular. Thus $\mathcal{J}_{\mathbb{B}}(F)$ is also regular. The assertion for $\mathcal{C}_{\mathbb{B}}(F)$ now follows from Eq. (3).
### 3 Topologies Related to Finite Automata

In this section we consider four shift-invariant topologies refining CANTOR topology. These topologies are closely related to finite automata. The first topology is the smallest topology having all regular $\omega$-languages which are also closed in CANTOR topology as open sets. This topology is remarkable because here all $\omega$-languages accepted by deterministic BÜCHI-automata are closed.

The subsequent two topologies are derived from Diekert's and Kufleitner's [3] alphabetic topology which is useful for investigations in restricted first-order theories for infinite words.

Finally, for the sake of completeness we add the topology having all regular $\omega$-languages as open (and closed) sets.

Every of the four considered topologies has an infinite set of isolated points. Thus in view of Lemma 1 none of them is a compact topology on $X^\omega$.

#### 3.1 The automatic topology

**Definition 2.** The automatic topology $\mathcal{T}_A$ on $X^\omega$ is defined by the base

$$ \mathbb{B}_A := \{F : F \subseteq X^\omega \wedge F \text{ is a regular } \omega\text{-language closed in CANTOR-space}\}. $$

It should be remarked that the sets (open balls) $w \cdot X^\omega$ are regular and closed in CANTOR-space. Moreover, the properties of regular $\omega$-languages show that $\mathbb{B}_A$ is shift-invariant. Thus the base $\mathbb{B}_A$ contains $\mathbb{B}_C$, and the automatic topology refines the CANTOR topology.

$\mathcal{T}_A$ has the following properties:

*Property 3.* 1. If $F \subseteq X^\omega$ is open (closed) in CANTOR topology $\mathcal{T}_C$ then $F$ is open (closed) in $\mathcal{T}_A$.

2. Every non-empty set open in $\mathcal{T}_A$ contains an ultimately periodic $\omega$-word.

3. The set $\mathcal{U}$ of ultimately periodic $\omega$-words is the set $\mathbb{I}_A$ of all isolated points in $\mathcal{T}_A$.

*Proof.* 1. and 2. are obvious.

3. Every $\omega$-language $\{w \cdot v^\omega\} = w \cdot \{v\}^\omega$ is regular and closed in CANTOR-space, and if $\{\xi\}$ is regular then $\xi$ is an ultimately periodic $\omega$-word.

The following theorem characterises the closure and the interior operators for the automatic topology. Here the second identity resembles the identity in Property 1.4.

**Theorem 3.**

$$ \mathcal{J}_A(F) = \bigcup_{E \in \mathbb{B}_A \setminus \{0\}} L(F; E) \cdot E \qquad (9) $$

$$ \mathcal{C}_A(F) = \bigcap \{W \cdot X^\omega : F \subseteq W \cdot X^\omega \wedge W \text{ is regular}\} \qquad (10) $$
*Proof.* The assertion of Eq.(9) is Lemma 3.

To prove Eq.(10) observe that, for regular $W \subseteq X^*$, the set $W \cdot X^\omega$ is closed in $T_A$. Thus the inclusion "$\subseteq$" is obvious.

Let, conversely, $\xi \notin C_A(F)$. Then there is a set $F' \in \mathbb{B}_A$ such that $\xi \in F'$ and $F \cap F' = \emptyset$. $F'$ is a regular $\omega$-language closed in $T_C$. Thus $X^\omega \setminus F' = W' \cdot X^\omega$ for some regular language $W' \subseteq X^*$. Consequently, $\xi \notin W' \cdot X^* \supseteq \bigcap \{W \cdot X^\omega : F \subseteq W \cdot X^\omega \wedge W \text{ is regular}\}$.

The next lemma describes sets open in $T_A$. As usual, a set is called nowhere dense if its closure does not contain a non-empty open subset.

**Lemma 6.** A set $F \subseteq X^\omega$ is open in $T_A$ if and only if

$$F = W \cdot X^\omega \cup \bigcup_{i \in \mathbb{N}} F_i$$

where the sets $F_i$ are regular, closed and nowhere dense in CANTOR-space.

*Proof.* If, in CANTOR-space, $F \subseteq X^\omega$ is closed then $F = V_F \cdot X^\omega \cup F'$ where $V_F = \{v : v \cdot X^\omega \subseteq F\}$ and $F'$ is nowhere dense and closed. If, moreover, $F$ is a regular $\omega$-language then $V_F \subseteq X^*$ is a regular language and, consequently, $F' = F \setminus V_F \cdot X^\omega$ is a regular $\omega$-language.

If $E$ is open in $T_A$ then $E$, as a union of base sets, has the form $E = W' \cdot X^\omega \cup \bigcup_{i \in \mathbb{N}} F_i$ where the $F_i$ are regular $\omega$-languages closed in CANTOR-space.

Now, from the preceding consideration we obtain the required form $E = (W' \cup \bigcup_{i \in \mathbb{N}} V_{F_i}) \cdot X^\omega \cup \bigcup_{i \in \mathbb{N}} F'_i$.

As an immediate consequence we obtain the following.

**Corollary 3.** Every set open in $T_A$ is an $F_\sigma$-set in CANTOR-space, and every set closed in $T_A$ is a $G_\delta$-set in CANTOR-space.

The converse of Corollary 3 is not true in general.

*Example 1.* Let $\eta \notin \text{Ult}$ and consider the countable $\omega$-language $F := \{0^n \cdot 1 \cdot \eta : n \in \mathbb{N}\}$.

Then, in CANTOR-space, $F = (\{0\}^\omega \cup F) \cap 0^* \cdot 1 \cdot \{0, 1\}^\omega$ is the intersection of a closed set with an open set, hence, simultaneously an $F_\sigma$-set and a $G_\delta$-set. As $F$ does not contain any ultimately periodic $\omega$-word, it cannot be open in $T_A$. Thus $X^\omega \setminus F$ is not closed in $T_A$.

Consequently, $0 \cdot F \cup 1 \cdot (X^\omega \setminus F)$ is a set being neither open nor closed in $T_A$ but being simultaneously an $F_\sigma$-set and a $G_\delta$-set in CANTOR-space. $\square$

For regular $\omega$-languages, however, we have the following. Here the second item shows a difference to the CANTOR topology.

**Proposition 1.** 1. Let $F \subseteq X^\omega$ be a regular $\omega$-language. Then $F$ is an $F_\sigma$-set in CANTOR-space if and only if $F$ is open in $T_A$, and $F$ is a $G_\delta$-set in CANTOR-space if and only if $F$ is closed in $T_A$.

2. There are clopen sets in $T_A$ which are not regular.
*Proof.* 1. In CANTOR-space, every regular $\omega$-language $F$ being an $F_\sigma$-set is a countable union of closed regular $\omega$-languages (see [16]).

2. The $\omega$-language $F_{\square} := \bigcup_{n \in \mathbb{N}} 0^{n^2} \cdot 1 \cdot X^{\omega}$ and its complement $X^{\omega} \setminus F_{\square} = \{0^{\omega}\} \cup \bigcup_{n \text{ is not a square}} 0^n \cdot 1 \cdot \tilde{X}^{\omega}$ partition the whole space $X^{\omega} = \{0, 1\}^{\omega}$ into two non-regular $\omega$-languages open in $T_A$.

## 3.2 Finite-state and regular $\omega$-languages

In this section we investigate whether finite-state and regular $\omega$-languages are preserved by $\mathcal{J}_A$ and $C_A$.

The first simple result is a consequence of Corollary 2.

**Proposition 2.** If $F \subseteq X^\omega$ is finite-state the also $\mathcal{J}_A(F)$ and $C_A(F)$ are finite-state $\omega$-languages.

It is, however, not true that the interior or the closure of finite-state $\omega$-languages are regular. To this end we consider the set $\text{Ult}$ of all ultimately periodic $\omega$-words.

*Example 2.* The set $\text{Ult} \subseteq X^\omega$ is the set of all isolated points of the topology $T_A$ hence open. Thus $\mathcal{J}_A(\text{Ult}) = \text{Ult}$.

Moreover $\text{Ult}/w = \text{Ult}$ for all $w \in X^*$, that is, $\text{Ult}$ is a one-state $\omega$-language, but $\text{Ult}$ is not regular. If we consider, for $a, b \in X$, $a \neq b$, the $\omega$-language $F = a \cdot \text{Ult} \cup b \cdot (X^\omega \setminus \text{Ult})$ then $F$ is finite-state and we obtain $\mathcal{J}_A(F) = a \cdot \text{Ult}$ and $C_A(F) = a \cdot X^\omega \cup b \cdot (X^\omega \setminus \text{Ult})$. So neither, $\mathcal{J}_A(F)$ nor $C_A(F)$ are regular $\omega$-languages. $\square$

A still more striking difference to CANTOR topology (see Property 1.5) is the fact that the closure (and also the interior) of a regular $\omega$-language need not be regular again.

*Example 3.* We use the fact (Lemma 2) that two regular $\omega$-languages $E, F$ already coincide if only $E \cap \text{Ult} = F \cap \text{Ult}$ and consider $C_A(\{0, 1\}^* \cdot 0^\omega)$.

Utilising Eq. (10) we get $C_A(\{0, 1\}^* \cdot 0^\omega) \subseteq \bigcap_{k \in \mathbb{N}} \{0, 1\}^* \cdot 0^k \cdot \{0, 1\}^\omega$. Consequently, $C_A(\{0, 1\}^* \cdot 0^\omega) \cap \text{Ult} = \{0, 1\}^* \cdot 0^\omega$.

If now, $C_A(\{0, 1\}^* \cdot 0^\omega)$ were a regular $\omega$-language, the identity $C_A(\{0, 1\}^* \cdot 0^\omega) = \{0, 1\}^* \cdot 0^\omega$ would follow. This implies, according to Corollary 3 that $\{0, 1\}^* \cdot 0^\omega$ is a $G_\delta$-set in CANTOR-space which is not true. $\square$

## 3.3 The alphabetic topologies

We start with the alphabetic topology which was introduced in [3]. Then we consider a variant of the alphabetic topology. We define both topologies by their respective bases.

**Definition 3.** The alphabetic topology is defined by the base

$$ \mathbb{B}_{\alpha} := \{w \cdot A^{\omega} : w \in X^{*} \wedge A \subseteq X\}. $$
All base sets are regular and closed, so the generated topology $\mathcal{T}_\alpha$ is coarser than the automatic topology $\mathcal{T}_A$.

For the next definition we fix the following notation (cf. [3]). For $A \subseteq X$ the $\omega$-language $A^{\text{im}}$ is the set of all $\omega$-words $\xi \in X^\omega$ where exactly the letters in $A$ occur infinitely often. In particular, $A^{\text{im}} = X^* \cdot A^{\text{im}}$.

**Definition 4.** The strong alphabetic topology is defined by the base

$$ \mathbb{B}_s := \{w \cdot (A^\omega \cap A^{\text{im}}) : w \in X^* \wedge A \subseteq X\}. $$

The $\omega$-languages in this base $\mathbb{B}_s$ are regular $\omega$-languages and $\mathbf{G}_\delta$-sets in CANTOR-space but, for $|A| \ge 2$, no $\mathbf{F}_\sigma$-sets in CANTOR-space. Thus they are closed but not open in the automatic topology. This shows that the strong alphabetic topology $\mathcal{T}_s$ does not coincide with $\mathcal{T}_A$.

For both alphabetic topologies suitable finite shift generators $M_\alpha$ and $M_s$ for the bases $\mathbb{B}_\alpha$ and $\mathbb{B}_s$, respectively, can be chosen in the following way:

$$ M_\alpha := \{A^\omega : A \subseteq X\} \text{ and } M_s := \{A^\omega \cap A^{\text{im}} : A \subseteq X\} $$

This yields the following property of the corresponding interior operators.

**Proposition 3.** $\mathcal{J}_\alpha(F) = \bigcup_{A \subseteq X} L(F; A^\omega) \cdot A^\omega$

$$ \mathcal{J}_s(F) = \bigcup_{A \subseteq X} L(F; A^\omega \cap A^{\text{im}}) \cdot (A^\omega \cap A^{\text{im}}) $$

With Corollary 2 we obtain the following.

**Corollary 4.** If $F \subseteq X^\omega$ is finite-state then $\mathcal{J}_\alpha(F)$, $\mathcal{C}_\alpha(F)$, $\mathcal{J}_s(F)$ and $\mathcal{C}_s(F)$ are regular $\omega$-languages.

*Proof.* Here it suffices to observe that the shift generators $M_\alpha := \{A^\omega : \emptyset \neq A \subseteq X\}$ and $M_s := \{A^\omega \cap A^{\text{im}} : \emptyset \neq A \subseteq X\}$ fulfil the assumption of Corollary 2.

Corollary 4 and Example 3 show that neither of the topologies $\mathcal{T}_\alpha$ and $\mathcal{T}_s$ coincides with the automatic topology $\mathcal{T}_A$.

This latter fact could be also obtained by considering the set of isolated points $\mathbb{I}_\alpha$ and $\mathbb{I}_s$ of the topologies $\mathcal{T}_\alpha$ and $\mathcal{T}_s$, respectively. Since for every isolated point $\xi$ the singleton $\{\xi\}$ has to be an element of every base of the topology, we obtain the identity

$$ \mathbb{I}_\alpha = \mathbb{I}_s = \{w \cdot a^\omega : w \in X^* \wedge a \in X\}. \quad (11) $$

## 3.4 The Büchi topology and the hierarchy of topologies

For the sake of completeness we introduce still another topology which we call Büchi topology because its base consists of all regular $\omega$-languages.

**Definition 5.** The Büchi topology is defined by the base

$$ \mathbb{B}_B := \{F : F \subseteq X^\omega \wedge F \text{ is a regular } \omega\text{-language}\}. $$
Here, trivially, closure and interior of regular $\omega$-languages are again regular.

What concerns closure and interior of regular $\omega$-langueges consider the set $F$ defined in Example 2. One easily verifies that $\mathcal{J}_B(F) = \mathcal{J}_A(F)$ and $\mathcal{C}_B(F) = \mathcal{C}_A(F)$.

So $F$ is an example of a finite-state $\omega$-language having non-regular interior and closure also with respect to $\mathcal{T}_B$. Thus, no base for the BÜCHI topology has a subset fulfilling the assumption of Corollary 2.2.

Arguing in the same way as for $\mathcal{T}_\alpha$ and $\mathcal{T}_s$ we obtain that the set of isolated points of the Büchi topology is $\mathbb{I}_B = \text{Ult}$.

Next we show that the following inclusion relation holds for the topologies considered so far. All inclusions are proper and other ones than the indicated do not exist.

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

First, the obvious inclusions $\mathbb{B}_B \supseteq \mathbb{B}_A \supseteq \mathbb{B}_\alpha \supseteq \mathbb{B}_C$ and $\mathbb{B}_B \supseteq \mathbb{B}_s$ imply the inclusions except for $\mathcal{T}_s \supseteq \mathcal{T}_\alpha$. This latter follows from the fact that in virtue of the identity

$$w \cdot A^\omega = \bigcup_{B \subseteq A} \bigcup_{v \in A^*} (w \cdot v \cdot B^\omega \cap B^{\text{im}}) \quad (12)$$

every base set of $\mathcal{T}_\alpha$ is open in $\mathcal{T}_s$.

To show the properness of the inclusions, we observe that the set of isolated points of the above topologies satisfy $\mathbb{I}_C = \emptyset$, $\mathbb{I}_\alpha = \mathbb{I}_s = \{w \cdot a^\omega : w \in X^* \wedge a \in X\}$ and $\mathbb{I}_A = \mathbb{I}_B = \text{Ult}$. Thus $\mathcal{T}_\alpha \neq \mathcal{T}_C$ and $\mathcal{T}_A \not\subseteq \mathcal{T}_s$.

The converse relation $\mathcal{T}_s \not\subseteq \mathcal{T}_A$ follows from the above mentioned fact that the sets $A^\omega \cap A^{\text{im}}$ for $2 \le |A| \le 3$ are open in $\mathcal{T}_s$ but, since they are regular $\omega$-languages not being $\mathbf{F}_\sigma$-sets in CANTOR-space, according to Proposition 1 not open in $\mathcal{T}_A$.

## 3.5 Metrisability

In this part we show that all the above topologies are metrisable. To this end we observe that for every topology, the sets contained in the above introduced bases are not only open but also closed. For $\mathcal{T}_C$ this is known, for $\mathcal{T}_\alpha$ and $\mathcal{T}_A$ the base sets are even closed in CANTOR-space. For $\mathcal{T}_B$ this follows because $\mathbb{B}_B$ is closed under complementation. Finally, the identity

$$X^\omega \setminus (w \cdot A^\omega \cap A^{\text{im}}) = \bigcup_{\substack{v \neq w \\ |v| = |w|}} v \cdot X^\omega \cup \bigcup_{B \neq A} B^{\text{im}} \quad (13)$$

shows that $\mathbb{B}_s$ consists of sets closed in $\mathcal{T}_s$.

To show the metrisability of all spaces we refer to Theorem 4.2.9 of [4] which states the following.
**Theorem 4.** Let $\mathcal{X}$ be a topological space with a countable base. Then $\mathcal{X}$ is metrisable if and only if $\mathcal{X}$ is a regular topological space.

A topological space $\mathcal{X}$ is called regular if every finite set is closed and for every point $p \in \mathcal{X}$ and every closed set $M \subseteq \mathcal{X}$, $p \notin M$, there are disjoint open sets $O_1, O_2$ such that $p \in O_1$ and $M \subseteq O_2$. In particular, this condition is satisfied if every finite subset of $\mathcal{X}$ is closed and $\mathcal{X}$ has a base consisting of closed sets.

Thus we obtain our result.

**Theorem 5.** Each of the topologies $T_C, T_\alpha, T_A, T_s$ and $T_B$ is metrisable.

# 4 Topologies Obtained by Adding Isolated Points

All topologies $T_A, T_B, T_s$ and $T_\alpha$ on $X^\omega$ considered so far have isolated points. In particular, all their isolated points belong to the set of ultimately periodic $\omega$-words Ult. In this section we are going to investigate in more detail topologies on $X^\omega$ which are obtained from CANTOR topology by adding all elements of a certain fixed set $\mathbb{I} \subseteq X^\omega$ as isolated points to the base $\mathbb{B}_C$.

**Definition 6.** Let $\mathbb{I} \subseteq X^\omega$. Define $T_\mathbb{I}$ as the topology $(X^\omega, \mathcal{O}_\mathbb{I})$ generated by the base $\mathbb{B}_\mathbb{I} := \mathbb{B}_C \cup \{\{\xi\} : \xi \in \mathbb{I}\}$.

## 4.1 General properties

First we characterise the closure $C_\mathbb{I}$ in the space $(X^\omega, \mathcal{O}_\mathbb{I})$. To this end observe that $\xi \notin C_\mathbb{I}(F)$ if and only if there is a base set $E \in \mathbb{B}_\mathbb{I}$ such that $\xi \in E$ and $E \cap F = \emptyset$. This yields the following.

$$X^\omega \setminus C_\mathbb{I}(F) = \bigcup \{w \cdot X^\omega : w \cdot X^\omega \cap F = \emptyset\} \cup (\mathbb{I} \setminus F) \quad (14)$$

By complementation, we obtain the following connection to the closure in CANTOR-space, $C(F) = \{\xi : \mathbf{pref}(\xi) \subseteq \mathbf{pref}(F)\}$.

$$ \begin{aligned} C_\mathbb{I}(F) &= C(F) \cap ((X^\omega \setminus \mathbb{I}) \cup F) \\ &= F \cup (C(F) \setminus \mathbb{I}) \end{aligned} \quad (15) $$

An immediate consequence of Eq. (15) is the following.

**Corollary 5.** If $F \supseteq X^\omega \setminus \mathbb{I}$ then $F$ is closed in $T_\mathbb{I}$.

We call a point $\xi \in X^\omega$ an accumulation point of a set $F \subseteq X^\omega$ with respect to a topology $\mathcal{T} = (X^\omega, \mathcal{O})$ provided every open set $E$ containing $\xi$ contains a point of $F \setminus \{\xi\}$. This is equivalent to the requirement that every base set (in any base for $(X^\omega, \mathcal{O})$) $E$ containing $\xi$ contains a point of $F \setminus \{\xi\}$.

**Theorem 6.** In the space $(X^\omega, \mathcal{O}_\mathbb{I})$ the set $X^\omega \setminus \mathbb{I}$ is the set of accumulation points of the whole space.
*Proof.* Let $M$ be the set of accumulation points of the whole space. Then, obviously, $M \cap \mathbb{I} = \emptyset$.

Conversely, if $\xi \notin \mathbb{I}$ then every base set containing $\xi$ is of the form $w \cdot X^\omega$, thus contains infinitely many points of $X^\omega$.

Next we turn to metrisability of the topologies. Since our spaces $(X^\omega, \mathcal{O}_\mathbb{I})$ do not necessarily have a countable base, we cannot conclude metrisability as in Theorem 5.

Therefore we use the HANAI-MORITA-STONE-Theorem (cf. [4, Theorem 4.47])

**Theorem 7 (Hanai, Morita, Stone).** Let $M_1 = (M_1, \mathcal{O}_1)$, $M_2 = (M_2, \mathcal{O}_2)$ be topological spaces. If $M_1$ is metrisable and there is a surjective mapping $\Psi : M_1 \to M_2$ such that $\Psi(M)$ is closed whenever $M \subseteq M_1$ is closed then the following are equivalent.

1. $M_2$ is metrisable, and

2. $M_2$ has a base $\mathbb{B}$ such that for every $m \in M_2$ the set $\mathbb{B}_m := \{B : B \in \mathbb{B} \wedge m \in B\}$ is countable.<fnref n="4" />

It is now obvious that every topological space $(X^\omega, \mathcal{O}_\mathbb{I})$ satisfies the Condition 2 of Theorem 7. In fact, for $\xi \in X^\omega$ it holds $\mathbb{B}_\mathbb{I},\xi = \{w \cdot X^\omega : w \sqsubseteq \xi\} \cup \{\xi\}$ or $\mathbb{B}_\mathbb{I},\xi = \{w \cdot X^\omega : w \sqsupseteq \xi\}$ according to whether $\xi \in \mathbb{I}$ or not.

If we use as $\Psi$ the identity mapping from CANTOR-space $(X^\omega, \mathcal{O}_C)$ to $(X^\omega, \mathcal{O}_\mathbb{I})$ then $\Psi$ trivially satisfies the hypothesis of the HANAI-MORITA-STONE-Theorem and we obtain the following.

**Theorem 8.** Let $\mathbb{I} \subseteq X^\omega$. Then the topology $\mathcal{T}_\mathbb{I} = (X^\omega, \mathcal{O}_\mathbb{I})$ is metrisable.

## 4.2 U-δ-topology

In this section we show that the topology $\mathcal{T}_\mathbb{I}$ admits a nice metrisation resembling Eq. (5) provided the set $\mathbb{I}$ is an $\mathbf{F}_\sigma$-set in CANTOR-space.

Let $U \subseteq X^*$ be a fixed language and define $U^\delta := \{\xi : \xi \in X^\omega \wedge |\mathbf{pref}(\xi) \cap U| = \aleph_0\}$. Then the following holds true.

**Lemma 7.** A subset $F \subseteq X^\omega$ is a $\mathbf{G}_\delta$-set in CANTOR-space if and only if there is a $U \subseteq X^*$ such that $F = U^\delta$.

Next, following [12], using the language $U$ we introduce a topology on $X^\omega$.

**Definition 7 (U-δ-topology).** The U-δ-topology of $X^\omega$ is the metric topology generated by the following metric

$$ \rho_U(\xi, \eta) := \begin{cases} 0, & \text{if } \xi = \eta, \text{ and} \\ |X| - |\mathbf{pref}(\xi) \cap \mathbf{pref}(\eta) \cap U|, & \text{otherwise.} \end{cases} $$

This topology has the following properties (see [12,14,15]). Denote by $C_U$ the topological closure induced by the metric $\rho_U$.

<footnote n="4">⁴ $M_2$ is second countable.</footnote>
**Proposition 4.** 1. In the $U$-$\delta$-topology of $X^\omega$ every point in $I_U := X^\omega \setminus U^\delta$ is an isolated point.

2. $C_U(F) = C(F) \cap (U^\delta \cup F) = F \cup (C(F) \cap U^\delta)$

Now Proposition 4.2 in connection with Eq. (15) shows that, for $\mathbb{I} := X^\omega \setminus U^\delta$ the $U$-$\delta$-topology of $X^\omega$ coincides with $\mathcal{T}_{\mathbb{I}}$.

Next we consider the set of isolated points of the topologies $\mathcal{T}_\alpha$, $\mathcal{T}_s$, $\mathcal{T}_A$ and $\mathcal{T}_B$. Recall that $I_\alpha = I_s = \bigcup_{a \in X} X^* \cdot a^\omega$ and $I_A = I_B = \text{Ult}$. Both sets are $\mathbf{F}_\sigma$-sets in CANTOR space. Thus the following holds true.

**Proposition 5.** One can construct languages $U_\alpha$ and $U_A$ such that the set of isolated points of the $U_\alpha$-$\delta$-topology of $X^\omega$ is $I_\alpha = \bigcup_{a \in X} X^* \cdot a^\omega$, and the set of isolated points of the $U_A$-$\delta$-topology of $X^\omega$ is $I_A = \text{Ult}$.

For the case $\mathbb{I} = \bigcup_{a \in X} X^* \cdot a^\omega$ one obtains a regular language $U_\alpha$.

**Corollary 6.** It holds $I_\alpha = X^\omega \setminus (\bigcup_{a,b \in X, a \neq b} X^* \cdot ab)^\delta$.

## 4.3 Shift-invariance

Finally, we derive a necessary and sufficient condition when a topology $\mathcal{T}_{\mathbb{I}}$ has a shift-invariant base. To this end we use the results of Section 2.

**Lemma 8.** A topology $\mathcal{T}_{\mathbb{I}}$ has a shift-invariant base if and only if $\mathbb{I} = \mathbb{I}/w$ for all $w \in X^*$.

*Proof.* For every isolated point $\xi \in \mathbb{I}$ the set $\{\xi\}$ is open in $\mathcal{T}_{\mathbb{I}}$. Thus according to Lemma 5 and Corollary 1 also $\{\xi\}/w$ and $\{w \cdot \xi\}$ are open. This shows the required identity.

Conversely, if $\mathbb{I} = \mathbb{I}/w$ for all $w \in X^*$ then, obviously, the base $\mathbb{B}_C \cup \{\{\xi\} : \xi \in \mathbb{I}\}$ is shift-invariant.

Having this necessary and sufficient condition one easily verifies that adding isolated points may result in non-shift-invariant refinements of CANTOR topology.

## References

1. Calude, C.S., Marcus, S. and Staiger, L., A topological characterization of random sequences, Inform. Process. Lett., Vol. 88 (2003), 245-250.

2. Calude, C.S., Jürgensen H., and Staiger, L., Topology on words, Theoret. Comput. Sci. 410 (2009), 2323-2335

3. Diekert, V. and Kufleitner, M., Fragments of first-order logic over infinite words, In (S. Albers and J.-Y. Marion, eds.), STACS 2009, Freiburg, Germany, February 26-28, 2009, Proceedings, 325-336. Online proceedings at DROPS and HAL, 2009.

4. Engelking, R., *General Topology*, Państwowe wydawnictwo naukowe, Warszawa 1977.

5. Fernau, H. and Staiger, L., Iterated function systems and control languages, Inform. and Comput., Vol. 168 (2001), 125-143.
6. Hoogeboom, H.J. and Rozenberg, G., Infinitary languages: Basic theory and applications to concurrent systems. In: Current Trends in Concurrency. Overviews and Tutorials (J.W. de Bakker, W.-P. de Roever and G. Rozenberg eds.), Lect. Notes Comput. Sci. 224, Springer-Verlag, Berlin 1986, 266–342.

7. Perrin, D. and Pin, J.-E., *Infinite Words*, Elsevier, Amsterdam 2004.

8. Prodinger, H.. Topologies on free monoids induced by closure operators of a special type. RAIRO Inform. Théor. Appl., 14(1980) 2, 225-237.

9. Redziejowski, R.R., Infinite word languages and continuous mappings. Theoret. Comput. Sci. 43 (1986) 1, 59–79.

10. Rozenberg, G. and Salomaa, A. (eds.), *Handbook of formal languages*, Springer, Berlin (1997).

11. Staiger, L., Finite-State ω-Languages, J. Comput. Syst. Sci. 27 (1983) 3, 434-448.

12. Staiger, L., Sequential Mappings of ω-Languages, ITA 21 (1987) 2, 147-173.

13. Staiger, L., ω-languages, In [10], Vol. 3, 339–387.

14. Staiger, L., Weighted Finite Automata and Metrics in Cantor Space, Journal of Automata, Languages and Combinatorics 8 (2003) 2, 353-360.

15. Staiger, L., Topologies for the Set of Disjunctive ω-words, Acta Cybern. 17 (2005) 1, 43-51.

16. Staiger, L., and Wagner, K., Automatentheoretische und automatenfreie Charakterisierungen topologischer Klassen regulärer Folgenmengen, Elektronische Informationsverarbeitung und Kybernetik, 10 (1974) 7, 379-392.

17. Thomas, W., Automata on Infinite Objects, in J. Van Leeuwen (Ed.), *Handbook of Theoretical Computer Science*, Vol. B, 133–191, Elsevier, Amsterdam, 1990.

18. Thomas, W., Languages, automata, and logic, In [10], Vol. 3, 389–455.

19. Trakhtenbrot, B.A., Finite automata and monadic second order logic, Sibirsk. Mat. Ž. 3 (1962), 103–131. (Russian; English translation: AMS Transl. 59 (1966), 23–55.)

20. Trakhtenbrot, B.A. and Barzdin, Ya.M., *Finite Automata, Behaviour and Synthesis Nauka Publishers, Moscow* 1970. (Russian; English translation: North Holland, Amsterdam 1973)