Words and Repeated Factors

Arturo Carpi  Aldo de Luca

Abstract

In this paper we consider sets of factors of a finite word which permit us to reconstruct the entire word. This analysis is based on the notion of box. The initial (resp. terminal) box of w is the shortest prefix (resp. suffix) of w which is an unrepeated factor. A factor u of w is a proper box if there are letters a, a′, b, b′ with a′ ≠ a, b′ ≠ b such that u = asb and a′s, sb′ are factors of w. A box is called maximal if it is not a proper factor of another box. The main result of the paper is the following theorem (maximal box theorem): Any finite word w is uniquely determined by the initial box, the terminal box and the set of maximal boxes. Another important combinatorial notion is that of superbox. A superbox is any factor of w of the kind asb, with a, b letters, such that s is a repeated factor, whereas as and sb are unrepeated factors. A theorem for superboxes similar to the maximal box theorem is proved. Some algorithms allowing us to construct boxes and superboxes and, conversely, to reconstruct the word are given. An extension of these results to languages is also presented.

1 Introduction

The study of the factors of finite as well as infinite words represents a topic of great interest in combinatorics on words. The number of factors of any length of a word (subword complexity) has been viewed as an evaluation of the richness of the structure of the considered word. However, for a finite word, it is sufficient to know its factors up to a certain length to reconstruct the entire word. For instance, it is easily seen that the only word whose factors of length 2 are ab, bc and cd is abcd.

The problem of reconstructing a word by knowing its ‘short’ factors appears in several fields. For instance, in analyzing DNA molecules, it is not possible to read the entire sequence of bases but only segments of limited length.

The aim of this paper is to study some sets of ‘short’ factors of a word which completely characterize the word itself, as well as the methods to reconstruct the word from such factors.

There are two combinatorial properties of factors of a word which turn out to be crucial for our purpose, namely repetition and extendability. Indeed, we shall show that the special factors (see e.g. [1, 5, 7, 8, 9, 10]), the shortest unrepeated initial and terminal factors and some related concepts are of fundamental importance in determining the ‘structure’ of the word itself.

We recall that a factor u of a finite word w is called right (resp. left) special if there exist two distinct extensions on the right (resp. on the left) in factors of w. A factor is bispecial if it is right and left special.

We shall introduce two classes of factors of a word, both of which uniquely determine the word. The first one is constituted by the boxes: the initial and terminal box of a word w are, respectively, the shortest prefix and suffix of w which are unrepeated factors while a proper box is any factor of w of the kind asb with a and b letters and s a bispecial factor of w. The second one is the set of the superboxes, which are factors of w of the kind asb with a and b letters, s a repeated factor of w and as, sb unrepeated factors of w.

In Sec. 4 we prove the surprising result, called the maximal box theorem (cf. Theorem 1), that any word is completely determined by the set of its (maximal) boxes and the initial and terminal boxes. A simple procedure to construct the word from the boxes is also given. A remarkable corollary is the following. Let K_{f} be the length of the terminal box of a word f and R_{f} be the minimal integer such that there are no right special factors of f of length R_{f}. If g is a word having the same set of factors as f up to the length n = max{R_{f}, K_{f}} + 1, then f = g. The value of n is optimal since one can prove that there exists a word g′ having the same set of factors of f up to the length n − 1, and, moreover, all the factors of f of length n are factors of g′ and all the factors of g′ of length n with the exception of one, are factors of f.

In Sec. 5 we study some interesting structural properties of boxes. In particular it is shown that the set of the maximal boxes in Theorem 1, is ‘nearly’ optimal because for any given word w one can construct another word v with the property that all boxes of w are factors of v, whereas there exist at most two boxes of v which are not factors of w. Moreover, we show that, starting from the set of maximal boxes of a word, one can construct the so-called ‘reduced sets’. An analog of the maximal box theorem for reduced sets holds. These sets are convenient, since they provide a simpler representation of the word.

In Sec. 6 the notion of superbox is studied. We prove a theorem showing that the initial and terminal boxes and the set of superboxes determine uniquely the word w. Moreover, we give two simple algorithms: the first allows us for any word w to determine the set of all superboxes and the second permits us to reconstruct the word starting from the set of all superboxes and the initial and terminal boxes.

In Sec. 7 we deal with languages and a box theorem for languages is presented. As a consequence of this result, we give a new proof of the Fine and Wilf ‘uniqueness theorem’ for periodic functions in the discrete case.

2 Preliminaries

Let A be a finite non-empty set or alphabet and A^{∗} the free monoid generated by A. The elements of A are usually called letters and those of A^{∗} words. The identity element of A^{∗} is called empty word and denoted by ϵ. We set A^{+} = A^{∗} \ {ϵ}.

A word w ∈ A^{+} can be written uniquely as w = w_{1}w_{2} ⋯ w_{n}, with w_{i} ∈ A, 1 ≤ i ≤ n, n > 0. The integer n is called the length of w and denoted |w|. The length of ϵ is 0. For any n ≥ 0, we denote by A^{n} the set of all the words of A^{∗} of length n and set A^{[n]} = ⋃_{i=0}^{n} A^{n}.

Let w ∈ A^{∗}. The word u ∈ A^{∗} is a factor (or subword) of w if there exist p, q ∈ A^{∗} such that w = puq. A factor u of w is called proper if u ≠ w.

If w = uq, for some q ∈ A^{∗} (resp. w = pu, for some p ∈ A^{∗}), then u is called a prefix (resp. a suffix) of w.

For any w ∈ A^{∗}, we denote respectively by F (w), Pref(w) and Suff(w) the sets of its factors, prefixes and suffixes.

We shall denote F (w) ∩ A by alph(w). This set represents the subset of the letters of A occurring in the word w.

For any X ⊆ A^{∗}, we set

F (X) = ⋃_{u∈X} F (u).

An element of F (X) will be also called a factor of X.

Let u ∈ F (w). Any pair (λ, μ) ∈ A^{∗} × A^{∗} such that w = λuμ is called an occurrence of u in w. If λ = ϵ (resp. μ = ϵ), then the occurrence of u is called initial (resp. terminal). An occurrence is called internal if it is neither initial nor terminal. An occurrence (λ, μ) of u in w is called leftmost (resp. rightmost) if the length of λ (resp. μ) is minimal. A factor u of w is called internal if there exists an internal occurrence of u in w.

Let w = w_{1}w_{2} ⋯ w_{n} (w_{i} ∈ A, 1 ≤ i ≤ n) be a word on the alphabet A. A set C ⊆ F (w) is a covering of w if, for any k = 1, …, n, there exist i, j, 1 ≤ i ≤ k ≤ j ≤ n, such that w_{i}w_{i+1} ⋯ w_{j} ∈ C.

Let us suppose Card(A) = d and consider in A^{∗} the prefix ordering of the words. It is well known that the graph associated with this order is a d-ary tree T_{d}, whose nodes represent the words of A^{∗} and the root represents the empty word.

With each finite word w, one can associate a finite subtree T_{w} of T_{d} obtained by taking all the nodes which represent factors of the word w. We call T_{w} the factor tree of w, since any factor of w will be represented by a node n of T_{w} or, equivalently, by a unique path going from the root to the node n.

If one replaces the prefix ordering of words by the suffix ordering one can construct in a similar way another tree T′_{w}, whose nodes represent the factors of w.

3 Repeated factors

A factor u of a word w is called repeated if there are at least two distinct occurrences of u in w. In the opposite case, the factor u is called unrepeated.

A factor u of w is extendable on the right (resp. left) in w if there exists a letter x ∈ A such that ux ∈ F (w) (resp. xu ∈ F (w)). The factor ux (resp. xu) of w is called a right (resp. left) extension of u in w.

If u is a factor of w, then the right (resp. left) valence of u is the integer Card({x ∈ A | ux ∈ F (w)}) (resp. Card({x ∈ A | xu ∈ F (w)})). The right (resp. left) valence of u is then the number, possibly 0, of all the distinct right (resp. left) extensions of u in w. In terms of the factor tree T_{w} (resp. T′_{w}) the right (resp. left) valence of u is the degree (that is the number of sons) of the node representing the factor u.

With each word w ∈ A^{∗} one can associate the factor k_{w} defined as the shortest suffix of w which is an unrepeated factor of w. This is also equivalent to say that k_{w} is the shortest factor of w which cannot be extended on the right in w, i.e. it has right valence equal to 0. The set of the factors of w which are not extendable on the right is given by A^{∗}k_{w} ∩ Suff(w). In the factor tree T_{w}, these factors are represented by the leaves. In a symmetric way, one can define h_{w} as the shortest prefix of w which cannot be extended on the left in w. Also in this case, the factors of w which are not extendable on the left are represented by the leaves of the tree T′_{w}.

In the following, we shall set K_{w} = |k_{w}| and H_{w} = |h_{w}|. If w ≠ ϵ, then one has 1 ≤ K_{w} ≤ |w| and 1 ≤ H_{w} ≤ |w|. If w = ϵ, then H_{ϵ} = K_{ϵ} = 0.

One can remark that all the proper prefixes of h_{w} and all the proper suffixes of k_{w} are repeated factors, while h_{w} and k_{w} are unrepeated.

In the following, for w ≠ ϵ, we shall denote by h′_{w} (resp. k′_{w}) the prefix (resp. suffix) of w of length H_{w} − 1 (resp. K_{w} − 1).

A word s is called a right (resp. left) special factor of w if there exist two letters x, y ∈ A, x ≠ y, such that sx, sy ∈ F (w) (resp. xs, ys ∈ F (w)).

A right (resp. left) special factor of w is then a repeated factor having at least two distinct extensions on the right (resp. left) in w, i.e. it has a right (resp. left) valence ≥ 2. This implies that a right (resp. left) special factor of w has at least an internal occurrence in w.

We remark that the set of right (resp. left) special factors is closed by suffixes (resp. prefixes).

A factor of w which is right and left special is called bispecial.

Let us remark that the empty word ϵ is always a bispecial factor of w, except when w is a power of a single letter. In such a case, w = k_{w} = h_{w}.

We denote by R_{w} (resp. L_{w}) the minimal non-negative integer such that there are no right (resp. left) special factors of length R_{w} (resp. L_{w}). One has 0 ≤ R_{w}, L_{w} ≤ |w|−1. Since the set of right special factors is closed by suffixes, there are no right special factors of length larger than R_{w}. Symmetrically, there are no left special factors of length larger than L_{w}.

A repeated factor of a word w is called maximal (with respect to the factorial order) if it is not a proper factor of another repeated factor of w.

Proposition 1 If a repeated factor u of a word w is maximal, then one of the following conditions is satisfied:

(i) u is a bispecial factor,

(ii) u = h′_{w},

(iii) u = k′_{w}.

Proof. Let us first suppose that u is a prefix of w. Since u is a repeated factor, then u has to be a prefix of h′_{w}. From the maximality, it follows that u = h′_{w}. In a symmetric way, one proves that if u is a suffix of w, then u = k′_{w}.

Let us then suppose that u is neither a prefix nor a suffix of w. Then, since u is repeated, there will exist two internal occurrences of u in w, and then letters x, x′, y, y′ ∈ A such that xuy, x′uy′ are two different occurrences of factors of w. Since u is a maximal repeated factor, it follows x ≠ x′ and y ≠ y′. Hence, u is a bispecial factor of w.

Let w ∈ A^{∗} be a non-empty word. We denote by G_{w} the maximal length of a repeated factor of w. The following proposition, whose proof we omit for the sake of brevity, holds [3, 6].

Proposition 2 Let w ∈ A^{+}. One has

G_{w} = max{R_{w}, K_{w}} − 1 = max{L_{w}, H_{w}} − 1.

Let us now for any word w ∈ A^{∗} introduce an important set of factors that we call boxes.

Let w ∈ A^{∗} be a word. A factor f of w is called a proper box of w if f = asb with a, b ∈ A and s is a bispecial factor. The factor h_{w} (resp. k_{w}) is called the initial (resp. terminal) box of w.

By box, without specification, we mean indifferently the initial, the terminal or a proper box.

A box is called maximal (with respect to the factorial order) if it is not a proper factor of another box.

The set of maximal boxes of w will be denoted by B_{w}. We note that, for any word, the initial, the terminal and the maximal boxes can be constructed by a simple algorithm, whose description is omitted.

4 Maximal box theorem

In this section we prove a theorem, called the ‘maximal box theorem’, which shows that if of a given word one knows the initial box, the terminal box and the set of the maximal boxes, then the word is uniquely determined. A simple procedure in order to reconstruct the word from the boxes is also given. A remarkable consequence of this theorem is that if two words f and g have the same set of factors up to the length n = max{R_{f}, K_{f}} + 1, then g = f. We prove also that this value of n is optimal.

Lemma 1 Let α be a box of w. Then any internal factor of α is repeated in w.

Proof. Let us first suppose that α = k_{w} and f is an internal factor of α. One has that f is a factor of k′_{w}, so that it is repeated in w. In a symmetrical way, one reaches the same result if f is an internal factor of α = h_{w}. Let us now suppose that α = asb is a proper box of w. An internal factor f of α is a factor of s, which is a bispecial factor of w. Since s is a repeated factor of w, so will be f.

Example 1 Let w be the word w = abccbabcab. One has h_{w} = abcc, k_{w} = cab. The proper boxes of w are ab, ba, bc, ca, cb, cc, abc, bca, bcc, cba, ccb. The maximal boxes are

abcc, bca, cab, cba, ccb.

Let w = abaababaaba. In this case h_{w} = abaabab, k_{w} = babaaba and these are the only maximal boxes of w.

For all n ≥ 0, we introduce the binary relation ⪯_{n} in A^{∗} defined as: for f, g ∈ A^{∗},

f ⪯_{n} g if and only if F (f) ∩ A^{[n]} ⊆ F (g) ∩ A^{[n]}.

One easily verifies that the relation ⪯_{n} is a well-founded quasi-order and, for all f, u, v ∈ A^{∗}, n ≥ 0, one has f ⪯_{n} ufv. We note that the intersection of the ⪯_{n} for all n ≥ 0 is the factorial order, that we denote by ⪯.

For all n ≥ 0, we consider the equivalence relation ∼_{n} = ⪯_{n} ∩ ⪯_{n}^{−1}. Thus

f ∼_{n} g if and only if F (f) ∩ A^{[n]} = F (g) ∩ A^{[n]}.

Theorem 1 (Maximal box theorem) Let f, g ∈ A^{∗} be two words such that

(i) h_{f} = h_{g}, k_{f} = k_{g},

(ii) B_{f} ⊆ F (g),

(iii) B_{g} ⊆ F (f).

Then f = g.

Proof. We prove, by induction, that for all n ≥ 0, f ∼_{n} g. Clearly, this implies that f = g.

Let us prove first the base of the induction, i.e. f ∼_{1} g. If Card(alph(f)) ≤ 1, then f = k_{f} = k_{g}. Thus, f ∈ F (g). Let us then suppose Card(alph(f)) > 1. In such a case, ϵ is a bispecial factor and any w ∈ A^{2} ∩ F (f) is a box. Since w is included in a maximal box, one has w ∈ F (g). Thus we have f ⪯_{1} g. In a symmetrical way, one proves that g ⪯_{1} f.

Now, let us prove the induction step. We suppose that n ≥ 1, f ∼_{n} g and prove that f ∼_{n+1} g.

Let w be a factor of f of length n + 1. If w is a box of f, then w is a factor of a maximal box and, therefore, by condition (ii), w is a factor of g.

Let us then suppose that w is not a box. We factorize w as w = atb, with a, b ∈ A, t ∈ A^{∗}, and t is not a bispecial factor of f. Since |at| = |tb| = n, by the inductive hypothesis, one has that at, tb ∈ F (g).

Let us first suppose that t is not a right special factor of f. Since at is extendable on the right in f, k_{g} = k_{f} cannot be a suffix of at. This implies that at can be extended on the right in g. Thus there exists a letter c such that atc ∈ F (g). By the inductive hypothesis, tc ∈ F (f). Since t is not right special in f, one obtains b = c and then atb ∈ F (g). With a symmetrical argument, if t is not a left special factor of f, one proves again that atb ∈ F (g). Thus we have obtained that f ⪯_{n} g. In a symmetrical way, one derives that g ⪯_{n} f.

Proposition 3 Let w be a word. If v is a factor of w, then there exists u ∈ Suff(v) such that for any a ∈ A

va ∈ F (w) if and only if (ua ∈ F (B_{w}) and va ∉ A^{+}h_{w}).  (1)

Proof. If v is not right extendable, then the statement is trivially verified by u = v. If Card(alph(w)) = 1, then the statement is verified by u = ϵ, since in this case h_{w} = w. If v = ϵ, then u = ϵ satisfies the condition.

Let us then suppose that v ≠ ϵ is right extendable and that Card(alph(w)) > 1. We can write

v = λbs, b ∈ A, λ ∈ A^{∗},

where s is the longest proper suffix of v which is a bispecial factor of w. We set u = bs. Let a be a letter of A and suppose va ∈ F (w). This trivially implies that va ∉ A^{+}h_{w}. Moreover, ua = bsa is a box so that ua ∈ F (B_{w}).

Conversely, let ua ∈ F (B_{w}), va ∉ A^{+}h_{w} and suppose, by contradiction, that va ∉ F (w). Let t be the longest suffix of v such that ta ∈ F (w). Since t ≠ v, one can write

v = μct, with c ∈ A, μ ∈ A^{∗} and cta ∉ F (w).

Since va ∉ A^{+}h_{w}, it follows that ta ≠ h_{w}. Thus, since t is left extendable in w, one derives that ta is left extendable in w, so that there exists a letter x ∈ A such that xta ∈ F (w). Moreover, since v is right extendable in w, there exists a letter y ∈ A such that cty ∈ F (w). One has x ≠ c and y ≠ a, since cta ∉ F (w). Hence, t is bispecial. This contradicts the fact that |t| ≥ |u| > |s|.

The previous proposition shows that if v is a right extendable factor of w, then to find a right extension of v it is sufficient to determine the longest suffix u of v in w such that there is at least one letter a ∈ A satisfying the right hand side condition of Eq. (1). For such a letter a one has va ∈ F (w).

Let us now give a simple procedure, based on Proposition 3, which allows us to construct the word w knowing the initial box h_{w}, the terminal box k_{w} and the set B_{w} of maximal boxes.

Let us write h_{w} = h′_{w}z, with z ∈ A.

Initially, we set p = h_{w}. Now suppose that we have already constructed a prefix p of w of length |p| ≥ H_{w}.

If p ∈ A^{∗}k_{w}, then the procedure ends and w = p. Otherwise, the right valence of p is 1. In order to extend p in w, we have to distinguish the following cases:

(i) p ∉ A^{∗}h′_{w}.

In this case, we search for the shortest suffix u of p which can be extended on the right in F (B_{w}) by a unique letter x and replace p by px.

Indeed, by Proposition 3, there exists a suffix of p which can be extended on the right in F (B_{w}) by a unique letter which is exactly the letter extending p on the right in w.

(ii) p ∈ A^{∗}h′_{w}.

In this case, we search for the shortest suffix u of p which can be extended on the right in F (B_{w}) by a unique letter x ∈ A \ {z} and replace p by px.

Indeed, by Proposition 3, there exists a suffix of p which can be extended on the right in F (B_{w}) by a unique letter in the set A \ {z} which is exactly the letter extending p on the right in w.

Proposition 4 Let f ∈ A^{∗} and n = R_{f} + 1. If g ∈ A^{∗} is such that g ∼_{n} f and k_{f} = k_{g}, then f = g.

Proof. Let us first prove that R_{f} = R_{g}. By the hypothesis, f and g have the same set of factors up to the length n = R_{f} + 1, so that all right special factors of f are also right special factors of g. Thus R_{f} ≤ R_{g}.

Let us suppose that R_{f} < R_{g}. Since the right special factors are closed by suffixes, there exists a right special factor of g of length R_{f}. This is also a right special factor of f, since f ∼_{R_{f} +1} g, and this is a contradiction. Thus R_{f} = R_{g} = R.

Remark that the length of any proper box of f or of g is at most n. Indeed, any proper box of f (resp. of g) can be written as asb with a, b ∈ A and s a bispecial factor of f (resp. of g). This implies that |asb| ≤ R + 1.

Hence, by the hypothesis that g ∼_{n} f, one derives that any proper maximal box of f is a factor of g and, conversely, any proper maximal box of g is a factor of f.

Since k_{f} = k_{g}, in view of Theorem 1, in order to prove f = g, it is sufficient to show that h_{f} = h_{g}.

Let us first suppose that |h_{f}| ≤ R. Then h_{f} is a factor of g which cannot be extended on the left in g because f ∼_{n} g. Thus h_{g} has to be a prefix of h_{f}. This implies |h_{g}| ≤ R, so that, by using the same argument, it follows that h_{f} has to be a prefix of h_{g}, and then h_{f} = h_{g}.

By a symmetrical argument, one arrives to the same conclusion if one supposes that |h_{g}| ≤ R.

Hence, we may suppose that |h_{f}|, |h_{g}| > R. This implies that h′_{f} (resp. h′_{g}) is not a right special factor of f (resp. g). Let us show that h′_{f} cannot be an internal factor of f. Indeed, otherwise there would exist letters x, y ∈ A such that h_{f} = h′_{f}x and h′_{f}y ∈ F (f). Since h_{f} is unrepeated then x ≠ y so that h′_{f} would be a right special factor of f. Thus, h′_{f} has to be a suffix of k′_{f}. Since k′_{f} is repeated, and h′_{f} is not an internal factor of f, the only possibility is that h′_{f} = k′_{f}. In a similar way, one has that h′_{g} = k′_{g}. By the hypothesis that k_{f} = k_{g}, one derives h′_{f} = k′_{f} = k′_{g} = h′_{g} = u.

Let h_{f} = ux and h_{g} = uy, x, y ∈ A. Let v be the suffix of u of length R. Since f ∼_{n} g, vx and vy are factors of both f and g. Since v is not right special, it follows x = y and h_{f} = h_{g}.

By a symmetric argument, the following proposition can be proved.

Proposition 5 Let f ∈ A^{∗} and n = L_{f} + 1. If g ∈ A^{∗} is such that g ∼_{n} f, and h_{f} = h_{g}, then f = g.

Theorem 2 Let f ∈ A^{∗} and n = max{R_{f}, K_{f}} + 1. For any g ∈ A^{∗}, if g ∼_{n} f, then g = f.

Proof. Let g ∼_{n} f. By Proposition 4, it is sufficient to prove that k_{f} = k_{g}.

Since f ∼_{n} g, then the factor k_{f} of f cannot be extended on the right in g, since otherwise k_{f} could be also extended on the right in f. Hence, k_{g} is a suffix of k_{f}. If k_{g} is a proper suffix of k_{f}, then k_{g} would be extendable on the right in f and, by hypothesis, also in g, which is a contradiction. Thus, k_{f} = k_{g}.

Proposition 6 Let f ∈ A^{∗} and n = max{R_{f}, K_{f}}. There exists g ∈ A^{∗} such that g ≠ f and g ∼_{n} f. Moreover, f ⪯_{n+1} g and all the factors of g of length n + 1, with the exception of one, are factors of f.

Proof. If f = ϵ, then n = 0 and the statement is trivially satisfied by g = a, a ∈ A. Let us then suppose f ≠ ϵ. By Proposition 2 the word f has a repetition of length n − 1, i.e. we can write

f = prq = p′rq′,

with |r| = n − 1 and |p| < |p′|.

Set g = p′rq. Let us prove that f ⪯_{n+1} g. Since |p′| > |p|, one has p′ = pξ with ξ ∈ A^{+} and then f = pξrq′. As |ξr| ≥ n, then a factor u of f of length n + 1 is either a factor of pξr = p′r or a factor of ξrq′ = rq, so that u is a factor of g.

Conversely, a factor of g of length n is either a factor of p′r or of rq and, therefore, it is a factor of f. This proves that f ∼_{n} g.

All factors of length n + 1 of g which occur in p′r or in rq are also factors of f. The only exception is given by xry, where x is the last letter of p′ and y is the first letter of q.

Example 2 Let A = {a, b, c} and w = abccbabcab. The factor abc is the right special factor of w of maximal length and k_{w} = cab. In this case, R_{w} = 4 and K_{w} = 3. We can write w = prq = p′rq′, where r = abc, p = ϵ, q = cbabcab, p′ = abccb and q′ = ab. Let us then consider the word g = p′rq = abccbabccbabcab. One easily verifies that g ∼_{4} w, w ⪯_{5} g and that babcc is the only factor of g of length 5 which is not a factor of w.

5 Boxes and reduced sets

In this section we prove some structural properties of boxes. In particular it is shown that any maximal box is an unrepeated factor. Moreover, one can prove that the set of the maximal boxes in the maximal box theorem is ‘nearly’ optimal in the sense that for any given word w one can construct another word v with the property that all boxes of w are factors of v, whereas there exist at most two boxes of v which are not factors of w. However, a simpler representation of a word is given by the so-called ‘reduced sets’ for which a result similar to the maximal box theorem holds.

Proposition 7 Let α be a maximal box of w. Then α is an unrepeated factor of w.

Proof. Suppose, by contradiction, that the maximal box α is a repeated factor of w. The box α will be a factor of a maximal repeated factor u of w. By Proposition 1, there are three possibilities:

1. u = h′_{w}. In such a case it follows that α is a proper factor of the initial box h_{w}, which contradicts the maximality of α as a box.

2. u = k′_{w}. In such a case it follows that α is a proper factor of the terminal box k_{w}, which contradicts the maximality of α as a box.

3. u is a bispecial factor of w. Since u has always an internal occurrence in w, it can be extended in a box. The same will occur for α, which contradicts again the maximality of α.

Proposition 8 Let w = λasbμ, where asb ≠ k_{w} (resp. asb ≠ h_{w}) is a proper maximal box of w with a, b ∈ A, s ∈ A^{∗}. If csb (resp. asc) is a box of w with c ∈ A and c ≠ a (resp. c ≠ b) having the leftmost (resp. rightmost) occurrence in w given by (λ′, μ′), then k_{w} = csbμ′ and μ′ ∈ Pref(μ) (resp. h_{w} = λ′asc and λ′ ∈ Suff(λ)).

Proof. We can write the word w as

w = λasbμ = λ′csbμ′.  (2)

First, we show that one of the words μ and μ′ is a prefix of the other one. Indeed, if it is not the case, we can write

μ = uxδ, μ′ = uyδ′

with x, y ∈ A, x ≠ y, u, δ, δ′ ∈ A^{∗}. Hence asbux, csbuy ∈ F (w). This implies that sbu is a bispecial factor, so that asbux is a box properly containing asb. This contradicts the maximality of asb.

Now, let us suppose that μ is a prefix of μ′. By Eq. (2), one has that asbμ is a suffix of w and sbμ is repeated in w. This implies that |asbμ| ≤ K_{w}. Since asb ≠ k_{w}, it follows that asb is a proper factor of k_{w}, which contradicts the maximality of asb as a box.

Thus μ′ is a prefix of μ. By Eq. (2), one has that csbμ′ is a suffix of w and sbμ′ is repeated in w. Consequently, csbμ′ is a suffix of k_{w}. If csbμ′ is a proper suffix of k_{w}, then it will be repeated and this contradicts the fact that (λ′, μ′) is the leftmost occurrence of csb in w. We conclude that k_{w} = csbμ′.

The remaining part of the proof is obtained by a symmetrical argument.

The following theorem [3], whose proof we omit, shows that for any given word w one can construct another word v with the property that all boxes of w are factors of v, whereas there exist at most two boxes of v which are not factors of w.

Theorem 3 Let w = λasbμ, where asb is a proper maximal box of w. Then, there exists a further occurrence of s in w, i.e. w = ξsη, such that the word v defined by

v = \{ \begin{matrix}λasη & if |λa| > |ξ| \\ ξsbμ & if |λa| < |ξ|, \end{matrix}  (3)

satisfies the following conditions:

(i) B_{w} ⊆ F (v),

(ii) 1 ≤ Card(B_{v} \ F (w)) ≤ 2.

Example 3 Let w be the word w = abccbabcab considered in Example 1. One has h_{w} = abcc, k_{w} = cab and the maximal boxes are

abcc, bca, cab, cba, ccb.

Let us underline in w the occurrences of the two maximal boxes bca and ccb:

w = ab\underline{ccb}abcab = abccba\underline{bca}b.

According to Theorem 3, we construct the word

v = abccba\underline{bcb}abcab.

One easily verifies that the maximal boxes of v are h_{v} = abcc, k_{v} = cab, ccbabcb and bcbabca. Moreover, B_{w} ⊆ F (v) and ccbabcb and bcbabca are the only two maximal boxes of v which are not factors of v.

Starting from the set of maximal boxes of a given word w, we introduce now the so-called reduced sets which also provide a representation of the word. These sets can be convenient since, as we shall see, the representation is simpler in the sense that any element of a reduced set is a factor of a maximal box.

Let f be a word and B_{f} be the set of its maximal boxes. We construct a new set D_{f} as follows. Let s be a bispecial factor of f and consider the set

Ω_{s} = {asb ∈ B_{f} | a, b ∈ A, as ∉ Suff(h′_{f}), sb ∉ Pref(k′_{f})}.

If Ω_{s} is not empty, we take arbitrarily one maximal box α = asb ∈ Ω_{s} and replace it by all boxes which are proper factors of it. Iterating these operations over all bispecial factors of f, we obtain a set of boxes. By deleting all elements which are not maximal, with respect to the factor order, we construct a set D_{f} that we call a reduced set of f.

We observe that, in the construction of D_{f}, it is sufficient to replace the maximal box α ∈ Ω_{s} by the longest box which is a proper prefix of α and the longest box which is a proper suffix of α. Indeed, it is easily seen that any other box in α will not appear in a reduced set. Moreover, by the construction, any box of f which is not maximal, is a factor of an element of D_{f}.

We remark that, by the arbitrary choice in each Ω_{s} of the maximal box to be replaced, one can obtain, in general, several distinct reduced sets.

Example 4 Let w be the word w = babacbcabaccbb. One has h_{w} = bab, k_{w} = bb. The bispecial factors of w are

ϵ, a, b, c, cb, abac.

The set of maximal boxes of w is

B_{w} = {bca, acbc, ccbb, babacb, cabacc}.

We can construct a reduced set D_{w} in the following way. We make the following replacements:

bca → bc, ca,
acbc → acb, cbc,
babacb → bab, acb.

By deleting all non-maximal elements, we obtain the reduced set

D_{w} = {bab, acb, cbc, ccbb, cabacc}.

The following theorem [3], which is an analog of the maximal box theorem, holds. The proof is omitted for the sake of brevity.

Theorem 4 Let f, g ∈ A^{∗} be two words and D_{f}, D_{g} be reduced sets of f and g, respectively. Suppose that

(i) h_{f} = h_{g}, k_{f} = k_{g},

(ii) D_{f} ⊆ F (g),

(iii) D_{g} ⊆ F (f).

Then f = g.

6 Superboxes

In this section we introduce the important notion of superbox which is strongly related to that of maximal box. An analog of the maximal box theorem is proved in the case of superboxes. Two simple algorithms are given, the first allows us to determine the superboxes of any word w, the second permits to reconstruct the word starting from h_{w}, k_{w} and the set of all superboxes.

Proposition 9 Let f = asb be a box of the word w with a, b ∈ A, s ∈ A^{∗} such that as and sb are unrepeated. Then f is a maximal box.

Proof. Suppose that asb is not maximal. Then, there exists a box α such that α = λasbμ, where λ, μ ∈ A^{∗} and λμ ≠ ϵ. It follows that either as or sb is an internal factor of α and then, by Lemma 1, a repeated factor of w, which is a contradiction.

We shall set

M_{w} = {asb ∈ F (w) | a, b ∈ A, s repeated and as, sb unrepeated.}

The elements of M_{w} will be called superboxes. The reason of this name is due to the fact that, as we shall prove by Proposition 13, any element of B_{w} \ {h_{w}, k_{w}} is a factor of an element of M_{w}.

Let us recall (cf. [2]) that a subset X of A^{∗} is called a factor code if no word of X is a proper factor of another word of X.

Proposition 10 Let w be a word. The set M_{w} is a factor code. Moreover, no element of M_{w} can be a factor of h_{w} or of k_{w}.

Proof. Suppose by contradiction that asb, ctd ∈ M_{w}, with a, b, c, d ∈ A, s, t ∈ A^{∗}, and that asb is a proper factor of ctd. This implies that either as or sb is a factor of t, which is absurd since t is a repeated factor of w. Suppose now that asb is a factor of h_{w} (resp. k_{w}). Then as (resp. sb) is a factor of h′_{w} (resp. k′_{w}) and then it is a repeated factor, which is a contradiction.

Proposition 11 Let f = asb ∈ M_{w} with a, b ∈ A and s ∈ A^{∗}. If s ≠ k′_{w} and s ≠ h′_{w}, then f is a proper maximal box.

Proof. Since s is a repeated factor of w, there will be at least another occurrence of s in w. Let us prove that we can always reduce ourselves to consider only the case when this occurrence is internal.

Let us suppose that s is a suffix of w. Then there exists a letter c such that cs is a suffix of w, and c ≠ a, since as is unrepeated. If |cs| < K_{w}, then cs is repeated and, therefore, s has a further internal occurrence in w. If |cs| > K_{w}, then |s| ≥ K_{w}. This implies that s is unrepeated, which is a contradiction. Finally, if |cs| = K_{w} one has s = k′_{w}, which contradicts the hypothesis made. The case when s is a prefix is dealt with a symmetric argument.

Let us consider then the case that the further occurrence of s is internal. In such a case, there exist two letters c, d ∈ A, for which csd ∈ F (w). One has c ≠ a and d ≠ b, because as and sb are unrepeated. This implies that s is a bispecial factor and that f = asb is a proper box. By Proposition 9, the result follows.

Proposition 12 Let asb be a proper maximal box of the word w, with a, b ∈ A and s ∈ A^{∗}. If sb (resp. as) is neither a prefix (resp. suffix) of k′_{w} nor of h′_{w}, then sb (resp. as) is unrepeated.

Proof. Suppose that sb is a repeated factor of w. If sb is a prefix of w, then sb has to be a prefix of h′_{w}, which has been excluded. Thus there is a letter c such that csb is a factor of w and c ≠ a, since asb is unrepeated by Proposition 7. By Proposition 8, one derives that csb is a prefix of k_{w} and then sb is a prefix of k′_{w}, which has been excluded. Thus, sb is unrepeated.

The remaining part of the proof is carried out in a symmetrical way.

Proposition 13 Any maximal box α of a word w, such that α ≠ h_{w} and α ≠ k_{w} is a factor of a superbox.

Proof. Let α = asb be a proper maximal box of w such that α ≠ h_{w} and α ≠ k_{w}. We consider the set of all factors of w of the kind f = xry where x, y ∈ A, r is a repeated factor of w and α is a factor of f.

Let us take in this set a maximal element, with respect to factor ordering, say β = ctd, with c, d ∈ A, t ∈ A^{∗}. Let us prove that β ∈ M_{w}. Let us first suppose that td is repeated. If β is right extendable, then one contradicts the maximality of β. If β is not right extendable, since td is repeated, then α ⪯ β = k_{w}. Since α ≠ k_{w}, one contradicts the maximality of α as a box. This proves that td is unrepeated. In a symmetric way, one shows that ct is unrepeated.

Proposition 14 The maximal boxes α ∈ B_{w} \{h_{w}, k_{w}} are either superboxes or prefixes or suffixes of elements of M_{w} ∩ A{h′_{w}, k′_{w}}A.

Proof. Let α ∈ B_{w} \ {h_{w}, k_{w}}. By Proposition 13, one has that α is a factor of a superbox β. Hence either α = β or α is a proper factor of β. In this latter case, β is not a maximal box. By Proposition 11, it follows that β ∈ A{h′_{w}, k′_{w}}A. Since α is a maximal box, α cannot be a factor of h′_{w} or of k′_{w} and then, necessarily, it is a prefix or a suffix of β.

Proposition 15 Let f, g ∈ A^{∗} be two words such that

(i) h_{f} ∈ Pref(g), k_{f} ∈ Suff(g), h_{g} ∈ Pref(f), k_{g} ∈ Suff(f),

(ii) M_{f} ⊆ F (g),

(iii) M_{g} ⊆ F (f).

Then f = g.

Proof. By Proposition 13, any element of B_{f} is a factor of an element of M_{f} ∪{h_{f}, k_{f}} and any element of B_{g} is a factor of an element of M_{g}∪{h_{g}, k_{g}}. Hence, B_{f} ⊆ F (g) and B_{g} ⊆ F (f). Thus, by the maximal box theorem, it is sufficient to prove that h_{f} = h_{g} and k_{f} = k_{g}.

Let us prove that h_{f} = h_{g}. By (i), we can write f as f = h_{f}ξ = h_{g}ξ′, ξ, ξ′ ∈ A^{∗} and g = h_{g}λ = h_{f}λ′, λ, λ′ ∈ A^{∗}. Let us suppose that |h_{f}| < |h_{g}|. This implies that h_{f} is a prefix of h′_{g} and then it is repeated in g.

We consider a further occurrence of h_{f} in g and a repeated factor α of g of maximal length containing as a factor such an occurrence of h_{f}. We can write g as g = δαμ with δ, μ ∈ A^{∗}. If δ and μ are non-empty, then there exist letters x and y such that xαy is a factor of g and xα, αy are unrepeated. Thus, xαy ∈ M_{g} and then xαy is a factor of f. One derives that in f there is a repeated occurrence of h_{f}, which is a contradiction. Now, suppose δ = ϵ. Since α is repeated, α is a proper prefix of h_{g} and, therefore, h_{f} has two occurrences in h_{g}. Since h_{g} ∈ F (f), this is a contradiction. Finally, if μ = ϵ, then α is a suffix of k′_{g} which, by (i), is a proper suffix of f. Thus α has a non-initial occurrence in f. Consequently h_{f} is repeated, which is a contradiction.

Thus, |h_{f}| ≥ |h_{g}|. Symmetrically, one can prove that |h_{g}| ≥ |h_{f}| and then h_{f} = h_{g}. In a symmetric way, one proves that k_{f} = k_{g}, which concludes the proof.

Let α, β ∈ A^{∗}. We denote by α ∧ β the maximal overlap of α with β, i.e. the suffix of maximal length of α which is a prefix of β. Then α and β can be written as α = λ(α ∧ β), β = (α ∧ β)μ, λ, μ ∈ A^{∗}. We shall denote by α ∨ β the word

α ∨ β = λ(α ∧ β)μ = αμ = λβ.

Lemma 2 Let u and v be two factors of a word w ∈ A^{∗}. If t is an unrepeated factor of w such that t ∈ Suff(u) ∩ Pref(v), then t = u ∧ v and u ∨ v ∈ F (w).

Proof. One has u = ξt and v = tη, where ξ, η ∈ A^{∗}. Since |t| ≤ |u ∧ v|, t is both a prefix and a suffix of u ∧ v. But t is unrepeated and, therefore, necessarily t = u ∧ v. Moreover, the only occurrence of t in w has to be preceded by ξ and followed by η, so that u ∨ v = ξtη ∈ F (w).

If t, u, v ∈ F (w) and both Suff(t) ∩ Pref(u) and Suff(u) ∩ Pref(v) contain elements which are unrepeated factors of w, then one has (t∨u)∨v = t∨(u∨v). Indeed, by an iterated application of Lemma 2, one has that (t ∨ u) ∨ v and t ∨ (u ∨ v) are both factors of w beginning by t and ending by v. They must coincide, since t and v are unrepeated in w.

More generally, if α_{0}, α_{1}, …, α_{n} ∈ F (w) and, for any i = 0, 1, …, n − 1, Suff(α_{i})∩Pref(α_{i+1}) contains an element which is an unrepeated factor of w, then one can consider the word α_{0} ∨ α_{1} ∨ ⋯ ∨ α_{n}, in which the parentheses are omitted since its value is independent from the order with which the operations are performed.

Let us now introduce a sequence Γ_{w} = (α_{0}, α_{1}, …, α_{n}) of elements of M_{w} ∪ {h_{w}, k_{w}} giving a covering of w. We shall call Γ_{w} also the covering sequence of w.

In the first step, we set α_{0} = h_{w}.

Now suppose that we have determined the element α_{i} ∈ M_{w} ∪ {h_{w}} (i ≥ 0). Let u be the shortest suffix of α_{i} which is unrepeated in w and write u = at with a ∈ A and t repeated in w. One can uniquely write w = λatμ, with λ, μ ∈ A^{∗}.

If tμ is a repeated factor of w, then, since atμ is unrepeated in w, one has atμ = k_{w}. In this case, we set α_{i+1} = k_{w} and this is the last element of the sequence. Otherwise, we set α_{i+1} = ar, where r is the shortest prefix of tμ which is unrepeated in w. In this latter case, one has r = sb, with b ∈ A and s is a repeated factor of w, while as is unrepeated in w, since it contains the prefix u = at. Thus, α_{i+1} ∈ M_{w}.

In other words, each element of the sequence Γ_{w}, excepted the first one, is obtained by taking the shortest suffix of the previous one which is unrepeated in w and extending it in w until one finds either a superbox or k_{w}.

Example 5 Let w be the word abccbabcab. The previous procedure generates the covering sequence of w

abcc, ccb, cba, babca, cab.

One has h_{w} = abcc and k_{w} = cab.

Proposition 16 Let w be a word and Γ_{w} = (α_{0}, α_{1}, …, α_{n}) be the covering sequence of w. Then one has

w = α_{0} ∨ α_{1} ∨ ⋯ ∨ α_{n}  (4)

and

M_{w} = {α_{1}, α_{2}, …, α_{n−1}}.  (5)

Proof. By the definition of Γ_{w}, for any i = 0, 1, …, n − 1, there is an unrepeated factor t of w such that t ∈ Suff(α_{i})∩Pref(α_{i+1}). Thus, by an iterated application of Lemma 2, one gets that the right hand side of Eq. (4) is a factor of w. Since it contains both h_{w} and k_{w} it must be necessarily equal to the entire w, so that Eq. (4) is proved.

Consequently, any factor of w either is a factor of an element of Γ_{w} or contains a word α_{i} ∧ α_{i+1} as an internal factor, for some i = 0, 1, …, n − 1. Since the words α_{i} ∧ α_{i+1} are unrepeated, they cannot occur as internal factors of a superbox and, therefore, any superbox is necessarily a factor of an element of Γ_{w}. In view of Proposition 10, one easily derives Eq. (5).

In the sequel, we shall denote M_{w} ∪ {h_{w}, k_{w}} by M′_{w}. Proposition 16 ensures that the elements of M′_{w} are exactly the elements of Γ_{w} and, therefore, M′_{w} is a covering of w. Let us observe that, in general, the set of maximal boxes B_{w} of the word w is not a covering. For instance, in the case of the word w = abcdebcd, one has B_{w} = {ab, de, ebcd} which is not a covering of w.

Next proposition shows that, once we know the initial box h_{w} of a word w and the set M′_{w}, we can effectively order the elements of M′_{w} to obtain Γ_{w}.

Proposition 17 Let w be a word and Γ_{w} = (α_{0}, α_{1}, …, α_{n}) be the covering sequence of w. Set δ_{i} = |α_{i} ∧ α_{i+1}|, 0 ≤ i ≤ n − 1. Then α_{i+1} is the only element β ∈ M′_{w} \ {α_{i}} such that |α_{i} ∧ β| ≥ δ_{i}.

Proof. Suppose β ∈ M′_{w} \ {α_{i}} and |α_{i} ∧ β| ≥ δ_{i}. Let u be the shortest suffix of α_{i} which is unrepeated in w. By the definition of Γ_{w}, u is a prefix of α_{i+1}, so that, by Lemma 2, |u| = |α_{i} ∧ α_{i+1}| = δ_{i} ≤ |α_{i} ∧ β|. One derives that u occurs in β. But, by the way the procedure for the construction of the covering sequence is carried out, the only elements of Γ_{w} in which u occurs are α_{i} and α_{i+1}, so that β = α_{i+1}.

To reconstruct a word w, knowing h_{w} and M′_{w}, first one has to arrange the elements of M′_{w} to obtain Γ_{w} and then use Eq. (4). The first operation is realized by observing that the first element of Γ_{w} is h_{w} and that each nonterminal element α_{i} of Γ_{w} is followed by the element β ∈ M′_{w} \ {α_{i}} such that the overlap of α_{i} with β has maximal length.

An unrepeated factor of w is called minimal if any of its proper factors is repeated. Let us denote by U_{w} the set of the minimal unrepeated factors of w.

Proposition 18 Let w be a word and Γ_{w} = (α_{0}, α_{1}, …, α_{n}) be the covering sequence of w. Then one has

U_{w} = {α_{0} ∧ α_{1}, α_{1} ∧ α_{2}, …, α_{n−1} ∧ α_{n}}.

Proof. By construction, the maximal overlap of an element α_{i} with the consecutive α_{i+1}, 0 ≤ i ≤ n − 1, is a minimal unrepeated factor of w.

Conversely, let u ∈ U_{w}. We can write uniquely w = λuμ, with λ, μ ∈ A^{∗}. Since u is minimal unrepeated, one has u = rb, with b ∈ A and r is a repeated factor of w. Thus w = λrbμ. If λr is repeated, since λrb is unrepeated, then λrb = h_{w}. Otherwise, consider the shortest unrepeated suffix of λr; we can write it as as, with a ∈ A and s is a repeated factor. Thus, in this case, since sb is unrepeated, asb ∈ M_{w}. Hence, in any case, u can be extended on the left in w in an element of Γ_{w}, say α_{i}, with 0 ≤ i ≤ n − 1. Moreover, u is the shortest suffix of α_{i} unrepeated in w, so that it is also a prefix of α_{i+1}. By Lemma 2, one has u = α_{i} ∧ α_{i+1}.

The following ‘uniqueness’ result was proved in [3]:

Proposition 19 Let w ∈ A^{∗}. Then w is the unique word of minimal length which begins by h_{w}, ends by k_{w} and contains the elements of M_{w} as factors.

In conclusion of this section, we mention that some general theorems relating Nerode’s equivalence of the language of the factors of a word and the theory presented in the previous sections are proved in [3].

7 A box theorem for languages

By language on the alphabet A we mean any non-empty subset L of A^{∗}. A language is called factorial if L = F (L). The notions of extendable factor, special factor and box can be naturally extended to languages, as follows.

A factor u of a language L is said to be right (resp. left) extendable in L if there exists a letter a ∈ A such that ua ∈ F (L) (resp. au ∈ F (L)). We shall denote by U_{L} the set of all factors of L which cannot be extended on the left in L, i.e.

U_{L} = {u ∈ F (L) | Au ∩ F (L) = ∅}.

In a symmetrical way, V_{L} will denote the set of all factors of L which cannot be extended on the right in L, i.e.

V_{L} = {u ∈ F (L) | uA ∩ F (L) = ∅}.

We shall denote by U_{L}^{0} (resp. V_{L}^{0}) the set of the elements of U_{L} (resp. V_{L}) which are minimal with respect to the prefix (resp. suffix) order. One has:

U_{L}^{0} = U_{L} \ U_{L}A^{+}, V_{L}^{0} = V_{L} \ A^{+}V_{L}.

Let L be a language over the alphabet A. A word s of A^{∗} is called a right (resp. left) special factor of L if there exist x, y ∈ A, x ≠ y, such that sx, sy ∈ F (L) (resp. xs, ys ∈ F (L)). A word of A^{∗} which is a right and left special factor of L is called a bispecial factor of L.

We introduce the set B_{L} of the proper boxes of L. A proper box α of L is a factor of L of the kind α = asb with a, b ∈ A and s a bispecial factor of L. Any element of U_{L}^{0} (resp. V_{L}^{0}) is called an initial (resp. terminal) box. By box, without specification, we mean indifferently an initial, a terminal or a proper box.

Let L, M be two languages over the alphabet A such that F (L) ≠ F (M). A separating factor of L and M is any word in the symmetric difference (F (L) \ F (M)) ∪ (F (M) \ F (L)). A minimal separating factor of L and M is a separating factor of minimal length.

The following lemma, whose proof is in [4], is the key result which allows us to prove a box theorem for languages.

Lemma 3 Let L, M ⊆ A^{∗} be two languages such that F (L) ≠ F (M) and let u be a minimal separating factor of L and M. Set p = max{2, |u|}. If the following conditions are satisfied

1) U_{L}^{0} ∩ A^{p−1} = U_{M}^{0} ∩ A^{p−1}, V_{L}^{0} ∩ A^{p−1} = V_{M}^{0} ∩ A^{p−1}

2) B_{L} ∩ A^{p} ⊆ F (M), B_{M} ∩ A^{p} ⊆ F (L),

then Card(alph(L)), Card(alph(M)) ≤ 1.

Theorem 5 Let L and M be languages on the alphabet A. If the following conditions are satisfied:

1) U_{L}^{0} = U_{M}^{0}, V_{L}^{0} = V_{M}^{0}

2) B_{L} ⊆ F (M), B_{M} ⊆ F (L),

then either F (L) = a^{∗}, F (M) = b^{∗}, with a, b ∈ A and a ≠ b, or F (L) = F (M).

Proof. We shall prove that if F (L) ≠ F (M), then F (L) = a^{∗}, F (M) = b^{∗}, with a, b ∈ A and a ≠ b.

By Lemma 3, one has Card(alph(L)), Card(alph(M)) ≤ 1. In such a case, either V_{L}^{0} ≠ ∅ and F (L) = F (V_{L}^{0}) or V_{L}^{0} = ∅ and L is an infinite language; similarly, one has that either V_{M}^{0} ≠ ∅ and F (M) = F (V_{M}^{0}) or V_{M}^{0} = ∅ and M is an infinite language. Thus, if V_{L}^{0} = V_{M}^{0} ≠ ∅, one would have

F (L) = F (V_{L}^{0}) = F (V_{M}^{0}) = F (M),

which is a contradiction. The only remaining possibility is that V_{L}^{0} = V_{M}^{0} = ∅ and L ⊆ a^{∗} and M ⊆ b^{∗} are infinite languages, with a ≠ b.

Let us observe that the preceeding theorem is, in fact, a box theorem for factorial languages (with the only exception of a trivial case). However, by using boardmarkers for the words of the language L, a box theorem for languages can be easily derived. More precisely, let us consider a new alphabet A_{0} = A ∪ {#}, where # ∉ A. For any language L ⊆ A^{∗}, we introduce the language

L̂ = #L#.

The following theorem holds [4].

Theorem 6 Let L and M be languages on the alphabet A such that

BL̂ ⊆ F (M̂), BM̂ ⊆ F (L̂).

Then L = M.

An infinite word f (from left to right) on the alphabet A is any map f : ℕ_{+} → A. We shall set for any i ≥ 1, f_{i} = f(i) and write

f = f_{1}f_{2} ⋯ f_{n} · · · .

A word u ∈ A^{∗} is a factor of f if u = ϵ or there exist integers i, j such that 1 ≤ i ≤ j and u = f_{i} ⋯ f_{j}. The set of all factors of f is denoted by F (f). A factor u of an infinite word f is called respectively right special, left special, bispecial if it is a right special, left special, bispecial factor of F (f). For an infinite word f we shall write B_{f}, U_{f}^{0} and V_{f}^{0} instead of B_{F (f)}, U_{F (f)}^{0} and V_{F (f)}^{0}.

An infinite word f is periodic of period p if for any i ≥ 1 one has f_{i} = f_{i+p}. As an application of Theorem 5, we shall give a new proof of the ‘unique-

ness theorem’ for periodic functions of Fine and Wilf [11], in the discrete case. We recall that this theorem can be stated as follows.

Theorem 7 Let f and g be two infinite periodic words of periods p and q, respectively. Let d = gcd(p, q). If

f_{1}f_{2} ⋯ f_{p+q−d} = g_{1}g_{2} ⋯ g_{p+q−d},

then f = g.

Proof. If p = q the result is trivial. Thus, we can always suppose p < q. Let us first consider the case that

gcd(p, q) = 1.

Set w = f_{1}f_{2} ⋯ f_{p+q−1} = g_{1}g_{2} ⋯ g_{p+q−1}. By the periodicity of f and g and the fact that |w| = p + q − 1 ≥ 2p − 1, one has

f ∼_{p} w ∼_{p} g.  (6)

Since the finite word w has period p, then as proved in [6], one has

R_{w} + 1 ≤ p.  (7)

By (6), f, g and w have the same right special factors up to the length p − 1. In particular, they have no right special factor of length R_{w}. Consequently, the length of a proper box of f or g is at most R_{w} + 1. By Eqs. (6) and (7) one derives

B_{f} ⊆ F (g), B_{g} ⊆ F (f).

Moreover, one has U_{f}^{0} = U_{g}^{0} = ∅ by the periodicity of f and g, and V_{f}^{0} = V_{g}^{0} = ∅ because f and g are infinite words (from left to right). Thus by Theorem 5 it follows either F (f) = a^{∗}, F (g) = b^{∗}, with a, b ∈ A and a ≠ b, or

F (f) = F (g).

The first case cannot occur in our case. Thus, from the previous equality, since f has period p, it follows that also g has period p. Since f and g have the same initial segment of length p, one derives f = g.

Let us now suppose that d > 1. For any r = 1, 2, …, d, consider the infinite words

f_{r}f_{r+d}f_{r+2d} ⋯ f_{r+nd} ⋯,
g_{r}g_{r+d}g_{r+2d} ⋯ g_{r+nd} · · · .

They have respectively periods \frac{p}{d} and \frac{q}{d}. Moreover they have the same initial segment of length \frac{p+q}{d} − 1 so that, by the preceding result, they are equal. It follows that f = g.

In conclusion, we mention that the notion of ‘special factor’ can be extended in a natural way to the case of sets of bidimensional words (pictures), taking into account right, left, up, and down extensions of subpictures. In this way, one can generalize in a suitable way the notion of box. A box theorem for picture languages, extending Theorem 6, is proved in [4].

References

[1] M.-P. Béal, F. Mignosi and A. Restivo, Minimal forbidden words and symbolic dynamics, Proc. STACS ’96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1046, 1996, pp. 555–566.

[2] J. Berstel and D. Perrin, Theory of codes, Academic Press, New York, 1985.

[3] A. Carpi and A. de Luca, Words and Special Factors, Preprint 98/33, Dipartimento di Matematica dell’Università di Roma ‘La Sapienza’, 1998.

[4] A. Carpi and A. de Luca, Repetitions and Boxes in Words and Pictures, Preprint 98/44, Dipartimento di Matematica dell’Università di Roma ‘La Sapienza’, 1998.

[5] J. Cassaigne, Complexité et facteurs speciaux, Bull. Belg. Math. Soc. 4 (1997) 67–88.

[6] A. de Luca, On the Combinatorics of Finite Words, Theoretical Computer Science, Special Issue for the workshop ‘Words’, to appear.

[7] A. de Luca and F. Mignosi, Some Combinatorial properties of Sturmian words, Theoretical Computer Science 136 (1994) 361–385.

[8] A. de Luca and L. Mione, On bispecial Factors of the Thue-Morse word, Information Processing Letters 49 (1994) 361–385.

[9] A. de Luca and S. Varricchio, On the factors of the Thue-Morse word on three symbols, Information Processing Letters 27 (1988) 281–285.

[10] A. de Luca and S. Varricchio, Some combinatorial problems of the Thue-Morse sequence and a problem in semigroups, Theoretical Computer Science 63 (1989) 333–348.

[11] N. J. Fine and H. S. Wilf, Uniqueness Theorem for Periodic Functions, Proc. Amer. Math. Soc., 16 (1965) 109–114.

Arturo Carpi  Aldo de Luca
Istituto di Cibernetica  Dipartimento di Matematica
CNR  Università di Roma ‘La Sapienza’
via Toiano, 6  piazzale Aldo Moro, 2
80072 Arco Felice (NA), Italy  00185 Roma, Italy

arturo@arturo.cib.na.cnr.it    deluca@mercurio.mat.uniroma1.it