On infinite real trace rational languages of maximum topological complexity ^{∗}

1Olivier Finkel and ^{2}Jean-Pierre Ressayre and ^{3}Pierre Simonnet

1,2Equipe de Logique Mathématique U.F.R. de Mathématiques, Université Paris 7 2 Place Jussieu 75251 Paris cedex 05, France. finkel@logique.jussieu.fr ressayre@logique.jussieu.fr

3UMR CNRS 6134, Faculté des Sciences, Université de Corse

Quartier Grossetti BP52 20250, Corte, France simonnet@univ-corse.fr

Abstract

We consider the set ℝ^{ω}(Γ, D) of infinite real traces, over a dependence alphabet (Γ, D) with no isolated letter, equipped with the topology induced by the prefix metric. We then prove that all rational languages of infinite real traces are analytic sets. We reprove also that there exist some rational languages of infinite real traces which are analytic but non Borel sets, and even Σ_{1}^{1}-complete, hence of maximum possible topological complexity. For that purpose we give an example of Σ_{1}^{1}-complete language which is fundamentally different from the known example of Σ_{1}^{1}-complete infinitary rational relation given in [Fin03c].

Keywords: Real traces; rational languages; topological properties; analytic and Borel sets.

1 Introduction

Trace monoids were firstly considered by Cartier and Foata for studying combinatorial problems, [CF69]. Next Mazurkiewicz introduced finite traces as a semantic model for concurrent systems, [Maz77]. Since then traces have been much investigated by various authors and they have been extended to infinite traces to model systems which may not terminate; see the handbook [DR95] and its chapter about infinite traces [GP95], for many results and references. In particular, real traces have been studied by Gastin, Petit and Zielonka, who characterized in [GPZ94] the two important families of recognizable and rational languages of real traces, over a dependence alphabet (Γ, D), in connection with rational languages of finite or infinite words. Several metrics have been defined on the set ℝ(Γ, D) of real traces over (Γ, D). In particular, the prefix metric defined by Kwiatkowska [Kwi90] and the Foata normal form metric defined by Bonnizzoni, Mauri and Pighizzini [BMP90]. Kummetz and Kuske stated in [KK03] that for finite dependence alphabets these two metrics define the same topology on ℝ(Γ, D). Moreover, if we consider only infinite real traces over a dependence alphabet (Γ, D) without isolated letter, the topological subspace ℝ^{ω}(Γ, D) = ℝ(Γ, D) − 𝕄(Γ, D) of ℝ(Γ, D) (where 𝕄(Γ, D) is the set of finite traces over (Γ, D)), is homeomorphic to the Cantor set 2^{ω}, or equivalently to any set Σ^{ω} of infinite words over a finite alphabet Σ, equipped with the product of the discrete topology on Σ, [KK03, Sta97a, PP04]. We can then define, from open subsets of the topological space ℝ^{ω}(Γ, D), the hierarchy of Borel sets by successive operations of countable intersections and countable unions. Furthermore, it is well known that there exist some subsets of the Cantor set, hence also some subsets of ℝ^{ω}(Γ, D), which are not Borel. There is another hierarchy beyond the Borel one, called the projective hierarchy.

∗The results of this paper have been exposed during the International Conference JAF 22, 22nd Journées sur les Arithmétiques Faibles, June 11-14, 2003, Napoli, Italy.

It is then natural to try to locate classical languages of infinite real traces with regard to these hierarchies and this question is posed by Lescow and Thomas in [LT94] (for the general case of infinite labelled partial orders like traces). In the case of infinite words, Mc Naughton’s Theorem implies that every ω-regular language is a boolean combination of Π_{2}^{0}-sets hence a Δ_{3}^{0} = (Σ_{3}^{0} ∩ Π_{3}^{0})-set. Landweber studied first the topological properties of ω-regular languages and characterized the ω-regular languages in each of the Borel classes Σ_{1}^{0}, Π_{1}^{0}, Σ_{2}^{0}, Π_{2}^{0}, [Lan69]. We study in this paper the topological complexity of rational languages of infinite real traces. We show below that all rational languages of infinite real traces are analytic sets and that there exist some rational languages of infinite real traces which are analytic but non Borel sets, and even Σ_{1}^{1}-complete, hence of maximum possible topological complexity, giving a partial answer to the question of the comparison between the topological complexity of rational languages of infinite words and of infinite traces [LT94].

The first author recently showed in [Fin03c] that there exists a Σ_{1}^{1}-complete infinitary rational relation R ⊆ Σ_{1}^{ω} ×Σ_{2}^{ω} where Σ_{1} and Σ_{2} are two finite alphabets having at least two letters. We could have used this result to prove that there exists a Σ_{1}^{1}-complete rational language of infinite real traces L ⊆ ℝ^{ω}(Γ, D), whenever (Γ, D) is a dependence alphabet and Γ ⊇ Σ_{1} ∪ Σ_{2}, where Σ_{1} and Σ_{2} are two independent dependence cliques having at least two letters. This can be done by considering the natural embedding i : Σ_{1}^{ω} × Σ_{2}^{ω} → ℝ^{ω}(Γ, D). The language R′ = i(R) is then Σ_{1}^{1}- complete. But this way the language R′ would have in fact the structure of an infinitary rational relation. On the other side the Σ_{1}^{1}-complete language L given in this paper is a new example whose structure is radically different from that of R′. In particular, L does not contain any Σ_{1}^{1}-complete language of infinite traces having the structure of an infinitary rational relation. This is important because in Trace Theory the structure of dependence alphabets is very important: some results are known to be true for some dependence alphabets and false for other dependence alphabets (see for example [HM97]).

Moreover we think that the presentation of this new example has also some interest for the following reasons. The proof given in this paper is self contained and is stated in the general context of traces. The problem is exposed in this general context and we use here the general properties of traces instead of the particular properties of infinitary rational relations. We use the characterization of rational languages of infinite real traces given by Theorem 2.1 of Gastin, Petit and Zielonka, which states a connection between rational languages of infinite words and rational languages of infinite real traces instead of the notion of Büchi transducer.

We prove also that all rational languages of infinite real traces are analytic. Our proof is not difficult, but it is original, using the Baire space ω^{ω} and the characterization of rational languages of infinite real traces given by Theorem 2.1: every rational language of infinite traces is a finite union of sets of the form R.S^{ω} where S and R are rational monoalphabetic languages of finite traces. This proof is rather different from usual ones in the theory of ω-languages. It uses a connection between the topological complexity of ω-powers of languages of finite traces, i.e. of languages of the form S^{ω}, where S is a language of finite traces, and the topological complexity of rational languages of infinite traces. The closure under countable union of the class of analytic sets is also important in the proof. We expect that the inverse way could also be fruitful: it seems to us that there should exist some context free ω-languages and some infinitary rational relations of high transfinite Borel rank. We think that we could use this fact to show that there exist ω-powers of finitary languages of high transfinite Borel rank. Notice that the question of the topological complexity of ω-powers (of languages of finite words) has been raised by several authors [Niw90, Sim92, Sta97a, Sta97b] and some new results have been recently proved [Fin01, Fin03a, Fin04b, Lec01].

The paper is organized as follows. In section 2 we recall the notion of words and traces. In section 3 we recall definitions of Borel and analytic sets, and we prove our main results in section 4.

2 Words and traces

Let us now introduce notations for words. For Σ a finite alphabet, a non empty finite word over Σ is a finite sequence of letters: x = a_{1}a_{2} … a_{n} where ∀i ∈ [1; n] a_{i} ∈ Σ. We shall denote x(i) = a_{i} the i^{th} letter of x and x[i] = x(1) … x(i) for i ≤ n. The length of x is |x| = n. The empty word will be denoted by ε and has no letters. Its length is 0. The set of non empty finite words over Σ is denoted Σ^{+}. Σ^{⋆} = Σ^{+} ∪ {ε} is the set of finite words over Σ. A (finitary) language L over Σ is a subset of Σ^{⋆}. The usual concatenation product of u and v will be denoted by u.v or just uv. For V ⊆ Σ^{⋆}, we denote V^{⋆} = {v_{1} … v_{n} | n ≥ 1 and ∀i ∈ [1; n] v_{i} ∈ V } ∪ {ε}.

The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a_{1}a_{2} … a_{n} …, where ∀i ≥ 1 a_{i} ∈ Σ. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) … σ(n) … and σ[n] = σ(1)σ(2) … σ(n) the finite word of length n, prefix of σ. The set of ω-words over the alphabet Σ is denoted by Σ^{ω}. An ω-language over an alphabet Σ is a subset of Σ^{ω}. For V ⊆ Σ^{⋆}, V^{ω} = {σ = u_{1} … u_{n} … ∈ Σ^{ω} | ∀i ≥ 1 u_{i} ∈ V } is the ω-power of V. The concatenation product is extended to the product of a finite word u and an ω-word v: the infinite word u.v is then the ω-word such that: (u.v)(k) = u(k) if k ≤ |u| , and (u.v)(k) = v(k − |u|) if k > |u|. The prefix relation is denoted ⊑: the finite word u is a prefix of the finite word v (respectively, the infinite word v), denoted u ⊑ v, if and only if there exists a finite word w (respectively, an infinite word w), such that v = u.w. We shall denote Σ^{∞} = Σ^{⋆} ∪ Σ^{ω} the set of finite or infinite words over Σ.

We introduce firstly traces as dependence graphs, [DR95, GP95, KK03]. A dependence relation over an alphabet Γ is a reflexive and symmetric relation on Γ. Its complement I_{D} = (Γ × Γ) − D is the independence relation induced by the relation D; the relation I_{D} is irreflexive and symmetric. A dependence alphabet (Γ, D) is formed by a finite alphabet Γ and a dependence relation D ⊆ Γ × Γ. A dependence graph [V, E, λ] over the dependence alphabet (Γ, D) is an isomorphism class of a node labelled graph (V, E, λ) such that (V, E) is a directed acyclic graph, V is at most countably infinite, λ : V → Γ is a function which associates a label λ(a) to each node a ∈ V, and such that:

(1) ∀v, w ∈ V (λ(v), λ(w)) ∈ D ↔ (v = w or (v, w) ∈ E or (w, v) ∈ E)

(2) The reflexive and transitive closure E^{⋆} of the edge relation E is well founded, i.e. there is no infinite strictly decreasing sequence of vertices.

Let us remark that, since in this definition (V, E) is acyclic, E^{⋆} is a partial order on V.

The empty trace has no vertice and will be denoted by ε as in the case of words.

As usually the concatenation of two dependence graphs g_{1} = [V_{1}, E_{1}, λ_{1}] and g_{2} = [V_{2}, E_{2}, λ_{2}], where we can assume, without loss of generality, that V_{1} and V_{2} are disjoint, is the dependence graph g_{1}.g_{2} = [V, E, λ] such that V = V_{1} ∪ V_{2}, E = E_{1} ∪ E_{2} ∪ {(v_{1}, v_{2}) ∈ V_{1} × V_{2} | (λ_{1}(v_{1}), λ_{2}(v_{2})) ∈ D}, and λ = λ_{1} ∪ λ_{2}.

The alphabet alph(t) of a trace t = [V, E, λ] is the set λ(V). The alphabet at infinity of t is the set alphinf(t) = {a ∈ Γ | λ^{−1}[a] is infinite } of all a ∈ alph(t) occurring infinitely often in t.

The set 𝕄(Γ, D) of finite traces over (Γ, D) is the set of traces having only finitely many vertices. For t ∈ 𝕄(Γ, D) the length of t is the number of vertices of t denoted |t|. The star operation T → T^{⋆} and the operation T → T^{ω} are naturally extended to subsets T of 𝕄(Γ, D): T^{⋆} = {t_{1}.t_{2} … t_{n} | n ≥ 1 and ∀i ∈ [1; n] t_{i} ∈ T } ∪ {ε} T^{ω} = {t_{1}.t_{2} … t_{n} … | ∀i t_{i} ∈ T }.

A real trace over (Γ, D) is a dependence graph [V, E, λ] such that for all v ∈ V the set {u ∈ V | (u, v) ∈ E^{⋆}} is finite. The set of real traces over (Γ, D) is denoted ℝ(Γ, D) and the set ℝ(Γ, D) − 𝕄(Γ, D) of infinite real traces will be denoted by ℝ^{ω}(Γ, D).

The prefix order over words can be extended to real traces in the following way. For all s, t ∈ ℝ(Γ, D) s ⊑ t iff there exists z ∈ ℝ(Γ, D) such that s.z = t iff s is a downwards closed subgraph of t. The corresponding suffix z is then unique.

Real traces may also be viewed as equivalence classes of (finite or infinite) words. Let (Γ, D) be a dependence alphabet and let φ : Γ^{∞} → ℝ(Γ, D) be the mapping defined by φ(a) = [{x}, ∅, x → a] for each a ∈ Γ and φ(a_{1}.a_{2} …) = φ(a_{1}).φ(a_{2}) … for each a_{1}.a_{2} … in Γ^{∞}. Let us remark that if there is some (a, b) in I_{D} then the mapping is not injective because for instance φ(ab) = φ(ba). One can define an equivalence relation ∼_{I} on Γ^{∞} by: for all u, v ∈ Γ^{∞} u ∼_{I} v iff φ(u) = φ(v). Then φ induces a surjective morphism from the free monoid Γ^{⋆} onto the monoid of finite dependence graphs 𝕄(Γ, D) = Γ^{⋆}/ ∼. And the set φ(Γ^{∞}) = Γ^{∞}/ ∼ is the set of real traces ℝ(Γ, D). The empty trace is the image φ(ε) of the empty word and is still denoted by ε.

We assume the reader to be familiar with the theory of formal languages and of ω-regular languages, see [Tho90, Sta97a, PP04] for many results and references. We recall that ω-regular languages are accepted by Büchi automata and that the class of ω-regular languages is the omega Kleene closure of the class of regular finitary languages. The family of rational real trace languages over (Γ, D) is the smallest family which contains the emptyset, all the singletons {[{x}, ∅, x → a]}, for a ∈ Γ, and which is closed under finite union, concatenation product, ⋆-iteration and ω-iteration on real traces. Let us now recall the following characterization of rational languages of infinite real traces (there exists also a version for finite or infinite traces, [GPZ94]). A real trace language R is said to be monoalphabetic if alph(s) = alph(t) for all s, t ∈ R.

Theorem 2.1 ([GPZ94]) Let T ⊆ ℝ^{ω}(Γ, D) be a language of infinite real traces over the dependence alphabet (Γ, D). The following assertions are equivalent:

(1) T is rational.

(2) T is a finite union of sets of the form R.S^{ω} where S and R are rational monoalphabetic languages of finite traces over (Γ, D) and ε ∉ S.

(3) T = φ(L) for some ω-regular language L ⊆ Γ^{ω}.

3 Topology

We assume the reader to be familiar with basic notions of topology which may be found in [Kec95, LT94, Sta97a, PP04]. There is a natural metric on the set Σ^{ω} of infinite words over a finite alphabet Σ which is called the prefix metric and defined as follows. For u, v ∈ Σ^{ω} and u ≠ v let d(u, v) = 2^{−l_{pref(u,v)}} where l_{pref(u,v)} is the first integer n such that the (n + 1)^{th} letter of u is different from the (n + 1)^{th} letter of v. This metric induces on Σ^{ω} the usual Cantor topology for which open subsets of Σ^{ω} are in the form W.Σ^{ω}, where W ⊆ Σ^{⋆}.

(Notice that this prefix metric may be extended to the set Σ^{∞} of finite or infinite words over the alphabet Σ).

The prefix metric has been extended to real traces by Kwiatkowska in [Kwi90] by defining firstly for all s, t ∈ ℝ(Γ, D) with s ≠ t:

l_{pref}(s, t) = sup{n ∈ ℕ | r ⊑ s ↔ r ⊑ t for all r ∈ 𝕄(Γ, D) with |r| ≤ n}

and next d_{pref}(s, t) = 2^{−l_{pref(s,t)}}

Notice that we consider in this paper infinite traces and Kwiatkowska defined the prefix metric over finite or infinite traces as one could also have done in the case of words. If D = Γ × Γ the prefix metric on infinite real traces over (Γ, D) coincide with the preceding definition in the case of infinite words over Γ.

If (Γ, D) is a dependence alphabet, a letter a ∈ Γ is said to be an isolated letter if a is independent from all other letters of Γ, i.e. ∀b ∈ Γ − {a}, (a, b) ∈ I_{D}. From now on we suppose that a dependence alphabet has no isolated letter. Then the set ℝ^{ω}(Γ, D) of infinite real traces over (Γ, D), equipped with the topology induced by the prefix metric, is homeomorphic to the Cantor set {0, 1}^{ω}, hence also to Σ^{ω} for every finite alphabet Σ having at least two letters [KK03].

Borel subsets of the Cantor set (hence also of topological spaces Σ^{ω} or ℝ^{ω}(Γ, D)) form a strict infinite hierarchy, the Borel hierarchy, which is defined from open sets by successive operations of countable unions and of countable intersections. We give the definition in the case of a topological space Σ^{ω}, the definition being similar in the case of the topological space ℝ^{ω}(Γ, D). Then we recall some well known properties of Borel sets.

Definition 3.1 The classes Σ_{n}^{0} and Π_{n}^{0} of the Borel Hierarchy on the topological space Σ^{ω} are defined as follows: Σ_{1}^{0} is the class of open subsets of Σ^{ω}. Π_{1}^{0} is the class of closed subsets, i.e. complements of open subsets, of Σ^{ω}. And for any integer n ≥ 1: Σ_{n+1}^{0} is the class of countable unions of Π_{n}^{0}-subsets of Σ^{ω}. Π_{n+1}^{0} is the class of countable intersections of Σ_{n}^{0}-subsets of Σ^{ω}. The Borel Hierarchy is also defined for transfinite levels. The classes Σ_{α}^{0} and Π_{α}^{0}, for a non-null countable ordinal α, are defined in the following way: Σ_{α}^{0} is the class of countable unions of subsets of Σ^{ω} in ∪_{γ<α}Π_{γ}^{0}. Π_{α}^{0} is the class of countable intersections of subsets of Σ^{ω} in ∪_{γ<α}Σ_{γ}^{0}.

Theorem 3.2

(a) Σ_{α}^{0} ∪ Π_{α}^{0} ⊊ Σ_{α+1}^{0} ∩ Π_{α+1}^{0}, for each countable ordinal α ≥ 1.

(b) ∪_{γ<α}Σ_{γ}^{0} = ∪_{γ<α}Π_{γ}^{0} ⊊ Σ_{α}^{0} ∩ Π_{α}^{0}, for each countable limit ordinal α.

(c) A set W ⊆ Σ^{ω} is in the class Σ_{α}^{0} iff its complement is in the class Π_{α}^{0}.

(d) Σ_{α}^{0} − Π_{α}^{0} ≠ ∅ and Π_{α}^{0} − Σ_{α}^{0} ≠ ∅ hold for every countable ordinal α ≥ 1.

We shall say that a subset of Σ^{ω} is a Borel set of rank α, for a countable ordinal α, iff it is in Σ_{α}^{0} ∪ Π_{α}^{0} but not in ⋃_{γ<α}(Σ_{γ}^{0} ∪ Π_{γ}^{0}).

Let us recall the characterization of Π_{2}^{0}-subsets of Σ^{ω}, involving the δ-limit W^{δ} of a finitary language W. For W ⊆ Σ^{⋆} and σ ∈ Σ^{ω}, σ ∈ W^{δ} iff σ has infinitely many prefixes in W, i.e. W^{δ} = {σ ∈ Σ^{ω}/∃^{ω}i such that σ[i] ∈ W } , see [Sta97a].

Proposition 3.3 A subset L of Σ^{ω} is a Π_{2}^{0}-subset of Σ^{ω} iff there exists a set W ⊆ Σ^{⋆} such that L = W^{δ}.

Example 3.4 Let Σ = {0, 1} and A = (0^{⋆}.1)^{ω} ⊆ Σ^{ω} be the set of ω-words over the alphabet Σ with infinitely many occurrences of the letter 1. It is well known that A is a Π_{2}^{0}-subset of Σ^{ω} because A = ((0^{⋆}.1)^{+})^{δ} holds.

There are some subsets of the Cantor set, (hence also of the topological spaces Σ^{ω} or ℝ^{ω}(Γ, D)) which are not Borel sets. There exists another hierarchy beyond the Borel hierarchy, called the projective hierarchy. Projective sets are defined from Borel sets by successive operations of projection and complementation. We shall only need in this paper the first class of the projective hierarchy: the class Σ_{1}^{1} of analytic sets. A set A ⊆ Σ^{ω} is analytic iff there exists a Borel set B ⊆ (Σ × Y)^{ω}, with Y a finite alphabet, such that x ∈ A ↔ ∃y ∈ Y^{ω} such that (x, y) ∈ B, where (x, y) ∈ (Σ × Y)^{ω} is defined by: (x, y)(i) = (x(i), y(i)) for all integers i ≥ 1. Analytic sets are also characterized as continuous images of the Baire space ω^{ω}, which is the set of infinite sequences of non negative integers. It may be seen as the set of infinite words over the infinite alphabet ω = {0, 1, 2, …}. The topology of the Baire space is then defined by a prefix metric which is just an extension of the previous one to the case of an infinite alphabet. A set A ⊆ Σ^{ω} (respectively A ⊆ ℝ^{ω}(Γ, D)) is then analytic iff there exists a continuous function f : ω^{ω} → Σ^{ω} (respectively f : ω^{ω} → ℝ^{ω}(Γ, D)) such that f(ω^{ω}) = A.

A Σ_{α}^{0} (respectively Π_{α}^{0}, Σ_{1}^{1})-complete set is a Σ_{α}^{0} (respectively Π_{α}^{0}, Σ_{1}^{1})- set which is in some sense a set of the highest topological complexity among the Σ_{α}^{0} (respectively Π_{α}^{0}, Σ_{1}^{1})- sets. This notion is defined via reductions by continuous functions. More precisely a set F ⊆ Σ^{ω} is said to be a Σ_{α}^{0} (respectively Π_{α}^{0}, Σ_{1}^{1})-complete set iff for any set E ⊆ Y^{ω} (with Y a finite alphabet): E ∈ Σ_{α}^{0} (respectively E ∈ Π_{α}^{0}, Σ_{1}^{1}) iff there exists a continuous function f such that E = f^{−1}(F). Σ_{n}^{0} (respectively Π_{n}^{0})-complete sets, with n an integer ≥ 1, are thoroughly characterized in [Sta86].

The ω-regular language A = (0^{⋆}.1)^{ω} given in Example 3.4 is a well known example of Π_{2}^{0}-complete set.

4 Rational languages of infinite traces

We want now to investigate the topological complexity of rational languages of infinite real traces. In a first step we shall give an upper bound of this complexity, showing that all rational languages T ⊆ ℝ^{ω}(Γ, D) are analytic sets.

We would like to use the characterization of rational languages T ⊆ ℝ^{ω}(Γ, D) given in item 3 of Theorem 2.1: T = φ(L) for some ω-regular language L ⊆ Γ^{ω}. Indeed every ω-regular language is a Borel set (of rank at most 3) and the continuous image of a Borel set is an analytic set. Unfortunately, the mapping φ is not continuous as the following example shows. Let (a, b) ∈ I_{D} and x_{n} ∈ Γ^{ω} defined by x_{n} = a^{n}ba^{ω} for each integer n ≥ 1. Then in Γ^{ω} the sequence (x_{n})_{n≥1} is convergent and its limit is a^{ω}. But the sequence (φ(x_{n}))_{n≥1} is constant in ℝ^{ω}(Γ, D) because for all n ≥ 1 φ(x_{n}) = φ(ba^{ω}). Thus the sequence (φ(x_{n}))_{n≥1} is convergent but its limit is φ(ba^{ω}) which is different from φ(a^{ω}).

We shall use the characterization of rational languages T ⊆ ℝ^{ω}(Γ, D) given in item 2 of Theorem 2.1: T is a finite union of sets of the form R.S^{ω} where S and R are rational monoalphabetic languages of finite traces over (Γ, D) and ε ∉ S. We consider firstly such rational languages in the simple form S^{ω} where S is a monoalphabetic language of finite traces over (Γ, D) which does not contain the empty trace. The set S is at most countable so it can be finite or countably infinite. In the first case card(S)=p and we can fix an enumeration of S by a bijective function ψ : {0, 1, 2, …, p − 1} → S and in the second case we can fix an enumeration of S by a bijective function ψ : ω = {0, 1, 2, …} → S. Let now H be the function defined from {0, 1, 2, …, p − 1}^{ω} (in the first case) or from ω^{ω} (in the second case) into ℝ^{ω}(Γ, D) by:

H(n_{1}n_{2} … n_{i} …) = ψ(n_{1}).ψ(n_{2}) … ψ(n_{i}) …

for all sequences n_{1}n_{2} … n_{i} … in {0, 1, 2, …, p − 1}^{ω} (in the first case) or in ω^{ω} (in the second case). It holds that H({0, 1, 2, …, p − 1}^{ω}) = S^{ω} (in the first case) or that H(ω^{ω}) = S^{ω} (in the second case). It is easy to see that H is a continuous function. A crucial point is that S is a monoalphabetic language, i.e. there exists Γ′ ⊆ Γ such that for all s ∈ S, alph(s) = Γ′. Let N = (n_{i})_{i≥1} and M = (m_{i})_{i≥1} be two infinite sequences of integers in {0, 1, 2, …, p − 1}^{ω} or in ω^{ω} such that for all i ≤ k n_{i} = m_{i}. Then r ⊑ H(N) ↔ r ⊑ H(M) holds (at least) for all r ∈ 𝕄(Γ, D) with |r| ≤ k. Thus l_{pref(H(N),H(M))} ≥ k and d_{pref}(H(N), H(M)) = 2^{−l_{pref(H(N),H(M))}} ≤ 2^{−k}. This implies that the function H is continuous (and even uniformly continuous).

If S is finite, then the set S^{ω} is the continuous image of the compact set {0, 1, 2, …, p − 1}^{ω} thus it is a closed hence also an analytic subset of ℝ^{ω}(Γ, D). If S is infinite, then the set S^{ω} is the continuous image of the Baire space ω^{ω} thus it is an analytic set.

Let now R ⊆ 𝕄(Γ, D) be a language of finite traces. For r ∈ R let θ_{r} : ℝ^{ω}(Γ, D) → ℝ^{ω}(Γ, D) be the function defined by θ_{r}(t) = r.t for all t ∈ ℝ^{ω}(Γ, D). It is easy to see that this function is continuous. Then r.S^{ω} = θ_{r}(S^{ω}) is an analytic set because the image of an analytic set by a continuous function is still an analytic set. The language R.S^{ω} = ⋃_{r∈R} r.S^{ω} is a countable union of analytic sets (because R is countable) but the class of analytic subsets of ℝ^{ω}(Γ, D) is closed under countable unions thus R.S^{ω} is an analytic set. A rational language T ⊆ ℝ^{ω}(Γ, D) is a finite union of sets of the form R.S^{ω} where S and R are rational monoalphabetic languages of finite traces over (Γ, D) and ε ∉ S. Then by finite union this language is an analytic set.

Notice that we have not used the fact that S and R are rational so the above proof can be applied to finite unions of sets of the form R.S^{ω} where S is a monoalphabetic language of finite traces and we have got the following result.

Proposition 4.1 Let (Γ, D) be a dependence alphabet without isolated letter, and let S_{i}, R_{i}, 1 ≤ i ≤ n, be languages of finite traces over (Γ, D), where, for all i, S_{i} does not contain the empty trace and is monoalphabetic. Then the language of infinite traces

T = ⋃_{1≤i≤n} R_{i}.S_{i}^{ω}

is an analytic set. In particular every rational language T ⊆ ℝ^{ω}(Γ, D) is an analytic set.

In order to prove the existence of Σ_{1}^{1}-complete rational language of infinite traces, we shall use results about languages of infinite binary trees whose nodes are labelled in a finite alphabet Σ having at least two letters. A node of an infinite binary tree is represented by a finite word over the alphabet {l, r} where r means “right” and l means “left”. Then an infinite binary tree whose nodes are labelled in Σ may be viewed as a function t : {l, r}^{⋆} → Σ. The set of infinite binary trees labelled in Σ will be denoted T_{Σ}^{ω}.

There is a natural topology on this set T_{Σ}^{ω} which is defined by the following distance, [LT94]. Let t and s be two distinct infinite trees in T_{Σ}^{ω}. Then the distance between t and s is \frac{1}{2^{n}} where n is the smallest integer such that t(x) ≠ s(x) for some word x ∈ {l, r}^{⋆} of length n. The open sets are then in the form T_{0}.T_{Σ}^{ω} where T_{0} is a set of finite labelled trees. T_{0}.T_{Σ}^{ω} is the set of infinite binary trees which extend some finite labelled binary tree t_{0} ∈ T_{0}, t_{0} is here a sort of prefix, an “initial subtree” of a tree in t_{0}.T_{Σ}^{ω}. It is well known that the topological space T_{Σ}^{ω} is homeomorphic to the Cantor set hence also to the topological spaces Σ^{ω} or ℝ^{ω}(Γ, D).

The Borel hierarchy and the projective hierarchy on T_{Σ}^{ω} are defined from open sets as in the cases of the topological spaces Σ^{ω} or ℝ^{ω}(Γ, D).

Let t be a tree. A branch B of t is a subset of the set of nodes of t which is linearly ordered by the tree partial order ⊑ and which is closed under prefix relation, i.e. if x and y are nodes of t such that y ∈ B and x ⊑ y then x ∈ B. A branch B of a tree is said to be maximal iff there is no other branch of t which strictly contains B.

Let t be an infinite binary tree in T_{Σ}^{ω}. If B is a maximal branch of t, then this branch is infinite. Let (u_{i})_{i≥0} be the enumeration of the nodes in B which is strictly increasing for the prefix order. The infinite sequence of labels of the nodes of such a maximal branch B, i.e. t(u_{0})t(u_{1})....t(u_{n})..... is called a path. It is an ω-word over the alphabet Σ.

For L ⊆ Σ^{ω} we denote P ath(L) the set of infinite trees t in T_{Σ}^{ω} such that t has at least one path in L.

It is well known that if L ⊆ Σ^{ω} is a Π_{2}^{0}-complete subset of Σ^{ω} (or a Borel set of higher complexity in the Borel hierarchy) then the set P ath(L) is a Σ_{1}^{1}-complete subset of T_{Σ}^{ω}, [Niw85, Sim93], [PP04, exercise].

In order to use this result we shall firstly code trees labelled in Σ by infinite words over the finite alphabet Γ = Σ ∪ Σ′ ∪ {A, B} where Σ′ = {a′ | a ∈ Σ} is a disjoint copy of the alphabet Σ and A, B are additional letters not in Σ ∪ Σ′.

Consider now the set {l, r}^{⋆} of nodes of binary infinite trees. For each integer n ≥ 0, call C_{n} the set of words of length n of {l, r}^{⋆}. Then C_{0} = {ε}, C_{1} = {l, r}, C_{2} = {ll, lr, rl, rr} and so on. C_{n} is the set of nodes which appear at the (n+1)^{th} level of an infinite binary tree. The number of nodes of C_{n} is card(C_{n}) = 2^{n}. We consider now the lexicographic order on C_{n} (assuming that l is before r for this order). Then, in the enumeration of the nodes with regard to this order, the nodes of C_{1} will be: l, r; the nodes of C_{3} will be: lll, llr, lrl, lrr, rll, rlr, rrl, rrr. Let u_{1}^{n}, …, u_{j}^{n}, …, u_{2^{n}}^{n} be such an enumeration of C_{n} in the lexicographic order and let v_{1}^{n}, ..., v_{j}^{n}, ..., v_{2^{n}}^{n} be the enumeration of the elements of C_{n} in the reverse order. Then for all integers n ≥ 0 and i, 1 ≤ i ≤ 2^{n}, it holds that v_{i}^{n} = u_{2^{n}+1−i}^{n}.

For t ∈ T_{Σ}^{ω} let U_{n}^{t} = t(u_{1}^{n})t(u_{2}^{n}) … t(u_{2^{n}}^{n}) be the finite word enumerating the labels of nodes in C_{n} in the lexicographic order, and let V_{n}^{t} = t(v_{1}^{n})t(v_{2}^{n}) … t(v_{2^{n}}^{n}) be the reverse sequence. Let V_{n}^{′t} = ψ(V_{n}^{t}) where ψ is the morphism from Σ^{⋆} into Σ^{′⋆} defined by ψ(a) = a′ for all a ∈ Σ. The code g(t) of t is then

g(t) = V_{0}^{′t}.A.U_{1}^{t}.B.V_{2}^{′t}.A.U_{3}^{t}.B.V_{4}^{′t}.A … A.U_{2n+1}^{t}.B.V_{2n+2}^{′t}.A …

The ω-word g(t) enumerates the labels of the nodes of the tree t which appear at successive levels 1, 2, 3, … The (images by ψ of) labels of nodes occuring at odd level 2n + 1 are enumerated in the reverse lexicographic order by the sequence V_{2n}^{′t} and the labels of nodes occuring at even level 2n are enumerated in the lexicographic order by the sequence U_{2n−1}^{t}. Labels of nodes of distinct levels are alternatively separated by a letter A or a letter B.

Let now (Γ, D) be a dependence alphabet where Γ = Σ ∪ Σ′ ∪ {A, B} and the independence relation I_{D} = Γ × Γ − D is defined by

I_{D} = Σ × ({A} ∪ Σ′) ⋃ ({A} ∪ Σ′) × Σ ⋃ Σ′ × {B} ⋃ {B} × Σ′

i.e. letters of Σ may only commute with A and with letters in Σ′ while letters of Σ′ may only commute with B and with letters in Σ, letter A (respectively B) may only commute with letters in Σ (respectively, with letters in Σ′).

Let now h : T_{Σ}^{ω} → ℝ^{ω}(Γ, D) be the function defined by:

∀t ∈ T_{Σ}^{ω} h(t) = φ(g(t))

We firstly state the following result.

Lemma 4.2 The above defined function h : T_{Σ}^{ω} → ℝ^{ω}(Γ, D) is continuous.

Proof. Let us remark that in a segment

B.V_{2n}^{′t}.A.U_{2n+1}^{t}.B.V_{2n+2}^{′t}.A

of an ω-word g(t) written as above, letters of U_{2n+1}^{t} may only commute with the preceding letter A and letters of V_{2n}^{′t}. In a similar manner letters of V_{2n+2}^{′t} may only commute with the preceding letter B and letters of U_{2n+1}^{t}.

So if two infinite binary trees t, s ∈ T_{Σ}^{ω} have the same labels on their k first levels, (k > 1), then for all r ∈ 𝕄(Γ, D) such that

|r| ≤ (k − 1) + 1 + 2 + 2^{2} + … + 2^{k−2}

it holds that

r ⊑ h(t) ↔ r ⊑ h(s)

So

l_{pref(h(t),h(s))} ≥ (k − 1) + 1 + 2 + 2^{2} + … + 2^{k−2} ≥ 2^{k−1}

and

d_{pref}((h(t), h(s)) = 2^{−l_{pref(h(t),h(s))}} ≤ 2^{−2^{k−1}}

so we have proved:

∀t, s ∈ T_{Σ}^{ω} d(t, s) ≤ 2^{−k} → d_{pref}((h(t), h(s)) ≤ 2^{−2^{k−1}}

Thus the function h is continuous (and even uniformly continuous). □

Let now R ⊆ Σ^{ω} be a regular ω-language. We are going to define from R a language of infinite real traces L over the dependence alphabet (Γ, D) defined above. Then we shall prove that L is rational and that P ath(R) = h^{−1}(L).

Let us firstly define L as being the set of infinite traces φ(σ) where σ ∈ Γ^{ω} may be written in the following form:

σ = x(1).u_{1}.A.v_{1}.x(2).u_{2}.B.v_{2}.x(3).u_{3}.A … A.v_{2n+1}.x(2n+2).u_{2n+2}.B.v_{2n+2}.x(2n+3).u_{2n+3}.A …

where for all integers i ≥ 0,

x(2i + 2) ∈ Σ and x(2i + 1) ∈ Σ′
u_{2i+2}, v_{2i+1} ∈ Σ^{⋆} and u_{2i+1}, v_{2i+2} ∈ Σ^{′⋆}
|v_{i}| = 2|u_{i}| or |v_{i}| = 2|u_{i}| + 1

and the ω-word x = ψ^{−1}(x(1))x(2)ψ^{−1}(x(3)) … x(2n)ψ^{−1}(x(2n + 1))x(2n + 2) … is in R.

Lemma 4.3 The above defined language L of infinite real traces is rational.

Proof. Every ω-word

σ = x(1).u_{1}.A.v_{1}.x(2).u_{2}.B.v_{2}.x(3).u_{3}.A … A.v_{2n+1}.x(2n+2).u_{2n+2}.B.v_{2n+2}.x(2n+3).u_{2n+3}.A …

written as above is equivalent, modulo the equivalence relation ∼_{I_{D}} over infinite words in Γ^{ω}, to the infinite word

σ′ = x(1).u_{1}.v_{1}.A.x(2).u_{2}.v_{2}.B.x(3).u_{3}.v_{3}.A … A.x(2n+2).u_{2n+2}.v_{2n+2}.B.x(2n+3).u_{2n+3}.v_{2n+3}.A …

But letters of Σ may commute also with letters of Σ′ and for all integers i,

|v_{i}| = 2|u_{i}| or |v_{i}| = 2|u_{i}| + 1

by definition of L. Thus every ω-word σ written as above is also equivalent, modulo ∼_{I_{D}}, to an infinite word in Γ^{ω} in the form

σ′′ = x(1).W_{1}.A.x(2).W_{2}.B.x(3).W_{3}.A … A.x(2n+2).W_{2n+2}.B.x(2n+3).W_{2n+3}.A …

where for all integers i ≥ 0,

W_{2i+1} ∈ (Σ′Σ^{2})^{⋆}.(Σ ∪ {ε})
W_{2i+2} ∈ (ΣΣ^{′2})^{⋆}.(Σ′ ∪ {ε})

Let L be the ω-language over the alphabet Γ formed by all such ω-words σ′′ such that x = ψ^{−1}(x(1))x(2)ψ^{−1}(x(3)) … x(2n)ψ^{−1}(x(2n + 1))x(2n + 2) … is in R. It is easy to see that L is an ω-regular language. Moreover L = φ(L) thus we can infer from Theorem 2.1 that L is a rational language of infinite real traces.

□

We are going now to prove the following result.

Lemma 4.4 For L defined as above from the ω-language R, it holds that P ath(R) = h^{−1}(L), i.e. ∀t ∈ T_{Σ}^{ω} h(t) ∈ L ⟷ t ∈ P ath(R).

Proof. Suppose that h(t) ∈ L for some t ∈ T_{Σ}^{ω}. Then h(t) = φ(g(t)) = φ(σ) where σ ∈ Γ^{ω} may be written in the following form:

σ = x(1).u_{1}.A.v_{1}.x(2).u_{2}.B.v_{2}.x(3).u_{3}.A … A.v_{2n+1}.x(2n+2).u_{2n+2}.B.v_{2n+2}.x(2n+3).u_{2n+3}.A …

where for all integers i ≥ 0,

x(2i + 2) ∈ Σ and x(2i + 1) ∈ Σ′
u_{2i+2}, v_{2i+1} ∈ Σ^{⋆} and u_{2i+1}, v_{2i+2} ∈ Σ^{′⋆}
|v_{i}| = 2|u_{i}| or |v_{i}| = 2|u_{i}| + 1

and the ω-word x = ψ^{−1}(x(1))x(2)ψ^{−1}(x(3)) … x(2n)ψ^{−1}(x(2n + 1))x(2n + 2) … is in R.

Then it is easy to see that σ = g(t), because of the definition of σ, of g(t), and of the independence relation I_{D} on Γ. Then ψ^{−1}(x(1)) = t(v_{1}^{0}) and u_{1} = ε, then |v_{1}| = 2|u_{1}| = 0 or |v_{1}| = 2|u_{1}|+1 = 1. If |v_{1}| = 0 then x(2) = t(u_{1}^{1}) and if |v_{1}| = 1 then x(2) = t(u_{2}^{1}). Then the choice of |v_{1}| = 2|u_{1}| or of |v_{1}| = 2|u_{1}| + 1 implies that x(2) is the label of the left or the rigth successor of the root node v_{1}^{0} = ε. This phenomenon will happen for next levels. The choice of |v_{i}| = 2|u_{i}| or of |v_{i}| = 2|u_{i}| + 1 determines one of the two successor nodes of a node at level i (whose label is x(i) if i is even or ψ^{−1}(x(i)) if i is odd) and then the label of this successor is ψ^{−1}(x(i + 1)) if i is even, or x(i + 1) if i is odd. Thus the successive choices determine a branch of t and the labels of nodes of this branch (changing only x(2n + 1) in ψ^{−1}(x(2n + 1))) form a path x = ψ^{−1}(x(1))x(2)ψ^{−1}(x(3)) … x(2n)ψ^{−1}(x(2n + 1))x(2n + 2) … which is in R. Then t ∈ P ath(R).

Conversely it is easy to see that if t ∈ P ath(R), the infinite word g(t) may be written as a word σ in the above form. Then h(t) = φ(g(t)) = φ(σ) is in L. □

We can now state the following

Theorem 4.5 There exist some Σ_{1}^{1}-complete, hence non Borel, rational languages of infinite real traces.

Proof. Suppose R ⊆ Σ^{ω} is a Π_{2}^{0}-complete ω-regular language. Let then L ⊆ ℝ^{ω}(Γ, D) be defined as above. L is a rational language of infinite real traces by Lemma 4.3. Then L is an analytic subset of ℝ^{ω}(Γ, D) by Proposition 4.1. But P ath(R) is a Σ_{1}^{1}-complete set and P ath(R) = h^{−1}(L) holds by Lemma 4.4 thus L is also Σ_{1}^{1}-complete. In particular L is not a Borel set. □

5 Concluding remarks

The existence of a Σ_{1}^{1}-complete infinitary rational relation has been used to get many undecidability results in [Fin03d] and the existence of a Σ_{1}^{1}-complete context free ω-language led to other undecidability results in [Fin03a, Fin03b, FS03]. In particular, the topological complexity and the degree of ambiguity of an infinitary rational relation or of a context free ω-language are highly undecidable. In a similar way, the existence of a Σ_{1}^{1}-complete recognizable language of infinite pictures, proved in [ATW02] by Altenbernd, Thomas, and Wöhrle, has been used in [Fin04a] to prove many undecidability results, giving in particular the answer to some open questions of [ATW02]. Topological arguments following from the existence of Σ_{1}^{1}-complete rational languages of infinite real traces can also be used to prove similar undecidability results for languages of infinite traces. In [FS03] have been established some links between the existence of a Σ_{1}^{1}- complete ω-language in the form V^{ω} and the number of decompositions of ωwords of V^{ω} in words of V. We think that such facts could be useful in the domain of combinatorics of traces. The code problem for traces is important in Trace Theory and several questions are still opened [HM97]. The analogue of the notion of ω-code and the study of the number of decompositions of infinite traces of V^{ω}, where V is a set of finite traces, in infinite product of traces of V, is also an important subject related to practical applications and to the notion of ambiguity (see [Aug01, AA01] for related results in the case of words). We think that topological arguments could be useful in this research area, and the existence of several Σ_{1}^{1}-complete languages of infinite traces, having different structures, could be useful in the cases of different dependence alphabets.

Acknowledgements. Thanks to the anonymous referees for useful comments on a preliminary version of this paper.

References

[Aug01] X. Augros, Des Algorithmes Autour des Codes Rationnels, Ph.D. Thesis, université de Nice-Sopia Antipolis, December 2001.

[AA01] M. K. Ahmad and X. Augros, Some Results on Codes for Generalized Factorizations, Journal of Automata, Languages and Combinatorics, Volume 6 (3), p. 239-251, 2001.

[ATW02] J-H. Altenbernd, W. Thomas and S. Wöhrle, Tiling Systems over Infinite Pictures and their Acceptance Conditions, in the Proceedings of the 6th International Conference on Developements in Language Theory, DLT 2002, Lecture Notes in Computer Science, Volume 2450, p. 297-306, Springer, 2003.

[BMP90] P. Bonnizzoni, G. Mauri and G. Pighizzini, About Infinite Traces, in V. Diekert, editor, Proceedings of the ASMICS Workshop Free Partially Commutative Monoids, Kochel am See, October 1989, Report TUM-I9002, pages 1-10, TU München, 1990.

[CF69] P. Cartier and D. Foata, Problèmes Combinatoires de Commutation et de Réarrangements, Volume 85 of Lecture Notes in Mathematics, Springer-Verlag, Berlin-Heidelberg-New York, 1969.

[DR95] V. Diekert and G. Rozenberg, Editors, The Book of Traces, World Scientific, Singapore, 1995.

[Fin01] O. Finkel, Topological Properties of Omega Context Free Languages, Theoretical Computer Science, Vol. 262 (1-2), July 2001, p. 669-697.

[Fin03a] O. Finkel, Borel Hierarchy and Omega Context Free Languages, Theoretical Computer Science, Vol 290 (3), 2003, p. 1385-1405.

[Fin03b] O. Finkel, Ambiguity in Omega Context Free Languages, Theoretical Computer Science, Volume 301 (1-3), 2003, p. 217-270.

[Fin03c] O. Finkel, On the Topological Complexity of Infinitary Rational Relations, RAIRO-Theoretical Informatics and Applications, Volume 37 (2), 2003, p. 105-113.

[Fin03d] O. Finkel, Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations, RAIRO-Theoretical Informatics and Applications, Volume 37 (2), 2003, p. 115-126.

[FS03] O. Finkel and P. Simonnet, Topology and Ambiguity in Omega Context Free Languages, Bulletin of the Belgian Mathematical Society, Volume 10 (5), 2003, p. 707-722.

[Fin04a] O. Finkel, On Recognizable Languages of Infinite Pictures, International Journal of Foundations of Computer Science, to appear. Available from http://www.logique.jussieu.fr/www.finkel

[Fin04b] O. Finkel, An ω-Power of a Finitary Language Which is a Borel Set of Infinite Rank, Fundamenta Informaticae, Volume 62 (3-4), 2004, p. 333-342.

[Gas91] P. Gastin, Recognizable and Rational Languages of Finite and Infinite Traces, Actes du STACS’91, Lecture Notes in Computer Science 480, p. 89-104, 1991.

[GP95] P. Gastin, A. Petit, Infinite Traces, Chapter in The Book of Traces, edited by V. Diekert et G. Rozenberg, World Scientific, p. 393-486, 1995.

[GPZ94] P. Gastin, A. Petit, W. Zielonka, An Extension of Kleene’s and Ochmanski’s Theorems to Infinite Traces, Fundamental Study, Theoretical Computer Science 125, p. 167-204, 1994.

[HM97] H.J. Hoogeboom and A. Muscholl, The Code Problem for Traces - Improving the Boundaries, Theoretical Computer Science 172, p. 309-321, 1997.

[Kec95] A.S. Kechris, Classical Descriptive Set Theory, Springer-Verlag, 1995.

[KK03] R. Kummetz and D. Kuske, The Topology of Mazurkiewicz Traces, Theoretical Computer Science, Volume 305 (1-3), p. 237-258, 2003.

[Kwi90] M. Kwiatkowska, A Metric for Traces, Information Processing Letters, 35, p. 129-135, 1990.

[Lan69] L. H. Landweber, Decision Problems for ω-Automata, Math. Syst. Theory 3 (1969) 4,376-384.

[Lec01] D. Lecomte, Sur les Ensembles de Phrases Infinies Constructibles a Partir d’un Dictionnaire sur un Alphabet Fini, Séminaire d’Initiation a l’Analyse, Volume 1, année 2001-2002.

[LT94] H. Lescow and W. Thomas, Logical Specifications of Infinite Computations, In:”A Decade of Concurrency” (J. W. de Bakker et al., eds), Springer LNCS 803 (1994), 583-621.

[Maz77] A. Mazurkiewicz, Concurrent Programs Schemes and their Interpretation, DAIMI Report PB-78, Aarhus University, Aarhus, 1977.

[Mos80] Y. N. Moschovakis, Descriptive Set Theory, North-Holland, Amsterdam 1980.

[Niw85] D. Niwinski, An example of Non Borel Set of Infinite Trees Recognizable by a Rabin Automaton, in Polish, Manuscript, University of Warsaw, 1985.

[Niw90] D. Niwinski, Problem on ω-Powers posed in the Proceedings of the 1990 Workshop “Logics and Recognizable Sets” (Univ. Kiel).

[PP04] D. Perrin and J.-E. Pin, Infinite Words, Automata, Semigroups, Logic and Games, Volume 141 of Pure and Applied Mathematics, Elsevier, 2004.

[Sim92] P. Simonnet, Automates et Théorie Descriptive, Ph. D. Thesis, Université Paris 7, March 1992.

[Sim93] P. Simonnet, Automate d’ Arbres Infinis et Choix Borélien, C.R.A.S. Paris, t.316, Série 1, p. 97-100, 1993.

[Sta86] L. Staiger, Hierarchies of Recursive ω-Languages, Jour. Inform. Process. Cybernetics EIK 22 (1986) 5/6, 219-241.

[Sta97a] L. Staiger, ω-Languages, Chapter of the Handbook of Formal languages, Vol 3, edited by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin.

[Sta97b] L. Staiger, On ω-Power Languages, in New Trends in Formal Languages, Control, Coperation, and Combinatorics, Lecture Notes in Computer Science 1218, Springer-Verlag, Berlin 1997, 377-393.

[Tho90] W. Thomas, Automata on Infinite Objects, in: J. Van Leeuwen, ed., Handbook of Theoretical Computer Science, Vol. B ( Elsevier, Amsterdam, 1990 ), p. 133-191.