INFORMATION AND CONTROL 59, 13--35 (1983) Repetition of Subwords in LOD Languages A. EHRENFEUCHT Department of Computer Science, University of ,odaroloC Boulder, Colorado, 80309 AND G. *GREBNEZOR Institute of Applied Mathematics and Computer Science, ytisrevinU of Leiden, Leiden, ehT Netherlands A language K c X* is repetitive if for each positive integer n there exists a word w E X + such that "w is a subword of K. Language K is called strongly repetitive if there exists a word w ~ X +, such that, for each positive integer n, w n is a subword of K. It is shown that it is decidable whether an arbitrary DOL language is repetitive. It is also shown that if a DOL language is repetitive then it is strongly repetitive. NOITCUDORTNI The investigation of the combinatorial structure of languages forms an important part of formal language theory. One of the most basic combinatorial structures of languages is the repetition of subwords (in words of a language). Roughly speaking, the investigation of repetitions of subwords can be divided into two (certainly not disjoint) directions. (1) The investigation of languages where repetitions of subwords (in the words of the language) are forbidden. This area was initiated by Thue IT in 1906 and since then this area was a subject of active investigation in numerous areas of mathematics and in formal language theory (see, e.g., BEM, C, MH, and S1). (2) The investigation of languages where repetitions of subwords (must) occur. The most classical example here is the class of context-free languages where the celebrated "pumping lemma" forces arbitrary long repetitions to be present in an infinite context-free language. * To whom all correspondence should be addressed. 13 0019-9958/83 $3.00 Copyright © 1983 by Academic Press, Inc. All rights of reproduction in any form reserved. 14 EHRENFEUCHT AND ROZENBERG Recently one notices a revival of interest in area (1) ("Thue problems") among formal language theorists (see, e.g., B, H, K, $2). In particular it was discovered that the theory of nonrepetitive sequences of Thue T is strongly related to the theory of DOL systems (see, e.g., RS). As a matter of fact it was pointed out in B that most (if not all) examples of the so- called square-free sequences constructed in the literature are either DOL sequences or their codings. Thus by now quite a lot is known about DOL languages (sequences) not containing repetitions of subwords (see also ER3I). On the other hand very little is known on DOL languages containing repetitive structures. The pumping-like properties do not hold for DOL languages and "detecting" repetitiveness in a DOL language becomes a challenging problem. This paper is devoted to the study of repetitiveness in DOL languages. Let us first make the notion of repetitiveness (of subwords in a language) more precise. We say that a language K ~ Z'* is repetitive if for each n/> 1 there exists a word wC Z +" such that w n is a subword of K. We say that K is strongly repetitive if there exists a word w E S + such that w n is a subword of a word of K for each n/> .1 It is easily seen that there exist repetitive languages that are not strongly repetitive, while on the other hand each strongly repetitive languages is obviously repetitive. By the pumping lemma infinite context-free languages are strongly repetitive. We demonstrate that (1) a DOL language is repetitive if and only if it is strongly repetitive and (2) it is decidable whether or not an arbitrary DOL system generates a repetitive language. 1. PRELIMINARIES We assume the reader to be familiar with the basic theory of DOL systems (see, e.g., RS). We will use the standard notation and terminology concerning DOL systems (as used in RS). Perhaps recalling the following notational matters will make the reading of this paper easier. N denotes the set of nonnegative integers and N + denotes the set of positive integers. For a set A, #A denotes its cardinality. A denotes the empty word. For a nonempty word w, first(w) denotes its first letter and last(w) denotes its last letter; for n C N, prefn(w) denotes the prefix of w of length n and subn(w ) denotes the set of subwords (segments) of w of length n. Then sub(w) denotes the set of all subwords of w and for a language K, REPETITION OF SUBWORDS 1 5 sub(K) = U~K sub(x). For a DOL system G = ,22( h, co), E(G) denotes its sequence, L(G) its language and max r(G)=max{izl:h(a)=z for some a C S}. A letter a ~ S is called alive if h'(a)4=A for all n C N+. We will use T(G) to denote the (infinite) derivation tree corresponding to E(G). For a node x in T(G), lb(x) denotes its label, anc(x) its direct ancestor and anc2(x) the direct ancestor of anc(x). Let E(G)= ,oOC col For a node x on the ..... level r >~ 0 of T(G) (counted top-down) and (an occurrence of) a subword z of soc where s >/r we use contrz(x) to denote the contribution of x to z; similarly if u is (an occurrence of) a subword in % then we use contr,(u) to denote the contribution of u to z. In order not to overburden the (already involved) notation: (1) we will often not distinguish notationally between a (sub)word and its occurrence, and (2) we will often not distinguish in our notation between nodes and their labels; as the precise meaning should be clear from the context, these conventions should not lead to a confusion. We will recall now two useful notions concerning DOL systems. Let G = (22, h, co) be a DOL system. A letter a C S has rank 0 (in G) (see, e.g., ER2) ifL(Ga) is finite, where G o = (22, h, a). Let for i >~ 1, S(i ) = 22 - {a ~ :22 a is of rank smaller than i} and let f(i) be the homomorphism of 22* defined by: f~i)(a)= a for a ~ S~i ) and f(i)(a)=A for a ~ 22- 22(i). Then let h(i ~ be the homomorphism of )~22 defined by h(i)(a ) =fu)(h(a)). If a letter a E 22(i) is such that the language of the DOL system (22(i), h(i), a) is finite then a has rank i (in G). For i >/0, we use ~22 to denote the set of all letters from 22 of rank i. Let G=(22, h, co) and G=(X,h, c0) be DOL systems. G is called a simplification of G if #~f< #22 and there exist homomomorphisms f: £'* *-- S*. g: S* --, 22* such that h = gf,/~ =fg, and Oc =f(co). If G does not have a simplification if is called elementary. It is known ER1 that if G is elementary then h is injective. If G 0, G1,..., Gn, n/>0, is the sequence of DOL systems such that G O = G, G i is a simplification of G i_l for 1 <~ i <~ n and G, is elementary, then G~ is called an elementary version of G. 2. BASIC DEFINITIONS AND RESULTS In this section we define some basic notions (and some basic results concerning them) to be investigated in this paper. These include the main notion of (strong) repetitiveness of a language as well as several more technical notions which will be useful for proving the main results of this paper. 2-3-1/95/346 61 EHRENFEUCHT AND ROZENBERG DEFINITION. Let K be a language, K c27". (1) K is repetitive if for each n E N + there exists a word w @ 72 + such that w n C sub(K). (2) K is strongly repetitive if there exists a word w E +72 such that w n E sub(K) for each n C NI + Obviously, if K is strongly repetitive then K is repetitive, but there exist repetitive languages, that are not strongly repetitive. Consider, e.g., the language K 0 ~_ {a, b, c, d} + defined by K 0 = {(wd)n:n E IN+, w E {a, b, c} +, l wl = n and for no x, yC {a,b, ct*,zE {a,b,e}+,w=xzzy}. Clearly K 0 is repetitive but not strongly repetitive language (notice that K is a context-sensitive language). DEFINITION. A DOL system G is called (strongly) repetitive if L(G) is (strongly) repetitive. The following special subclass of DOL systems will be useful in the considerations of the next section. DEFINITION. A DOL system G = (Z, h, co) is pushy if sub(L(G)) N Z* is infinite; otherwise G is not pushy. If a DOL system G is not pushy then q(G) denotes max{w: w C sub(L(G)) ~ 27* .} LEMMA 2.1. (1) It is decidable whether or not an arbitrary DOL system is pushy. (2) If a DOL system G = (Z, h, )oc is not pushy then 72 i = J( for all i>0. (3) If a DOE system G is not pushy then q(G) is effectively computable. Proof. (1) Let G = (27, h, co) be a DOL system. We say that G satisfies the edge condition if the following holds: there exists xEZ, kEN + , w~27", and u@Z + such that alph(u) contains an alive letter and either hk(x)= wxu or h~(x)= uxw. We observe that G is pushy if and only if G satisfies the edge condition. This is seen as follows. Obviously, if G satisfies the edge condition then G is pushy. Assume now that G is pushy. Then sub(L(G)) contains arbitrary long words over Z o. Consider now a word z E 27+ ~ sub(L(G)), it appears as a 17 REPETITION OF SUBWORDS subword of oc T for some r C N +, where E(G) = oc o, col ,.... Thus we have the situation depicted in Fig. 1, where l z is the first to the left of z occurrence of a letter not in o22 and r z is the first to the right of z occurrence of a letter not in 22 0. Clearly z can be chosen so that at least one of lz, rz must exist as otherwise L(G) would be finite and so G could not be pushy. Assume that both ~l and ~r exist; if only one of them exist, the reasoning is even simpler. Then Pl(Pr) is the path leading from a node in oc o to lz(rz). Since z can be chosen arbitrarily long (at least) one of the following conditions must hold. (i) Pl contains different nodes n ,1 n 2 such that lb(nl)= lb(n2), and both contru(nl) and contru(n2) contain (an occurrence of) an alive letter; (ii) Pr contains different nodes mi, m 2 such that lb(ml)= lb(m2) and both contr,(ml) and contru(m2) contain (an occurrence of) an alive letter. Then it is easily seen that G must satisfy the edge condition. Now (1) follows from an easy observation that the edge condition is decidable (it is well known that it is decidable whether an arbitrary letter is in 22 0 and whether an arbitrary letter is alive). (2) This follows directly from the definition of a letter with rank i > 0. (3) Assume that G = (Z', h, co) is not pushy, then q(G) exists. Clearly q(a) = min{n ~ N+ : 022 * ~ subn+l(L(G)) = .}O Thus to find q(G) it suffices to construct in succession sets *22 ~ subi(L(G)), i = 1, 2,..., until one of these sets becomes empty--if this happens for the index i 0 then q(G) = i 0 -- 1. The existence of q(G) guarantees the termination of this algorithm. II Our next notion is the fundamental technical notion of this paper. z \ z Z \ / \ / \ ! \ / \ FIGURE 18 EHRENFEUCHT AND ROZENBERG .NOITINIFED A DOL system G = ,22( h, )~o is called special, abbreviated a SDOL system, if it satisfies the following conditions. (0) G is reduced. (1) G is sliced meaning that (1.1) for each a C Z', and each n ~ N +, alph(h~(a)) = alph(h(a)), (1.2) for each aEZ, the length sequence o~>~}l)a(nhI{ is either strictly increasing or constant and (1.3) o)~X. (2) G is strongly growing meaning that (2.1) G is propagating and (2.2) no letter in G has a rank (including the zero rank). (3) G is elementary. The next few results bind the notion of repetitiveness with several subclasses of DOL systems as well as they indicate how this notion carries over through some operations on languages and DOL systems. AMMEL 2.2. Let G be a DOL system. (1) If G is pushy then G is strongly repetitive. (2) If G is JTnite then G is not repetitive. Proof (1) This follows easily from the observation made in the proof of Lemma 1.2 that the edge condition is equivalent to the pushy property. (2) Obvious. II .NOITINIFED Let K be a language and let (K 1 ,..., Kn), n /> ,1 be a n-tuple of languages. Then K < (K 1,..., Kn) if K c K1K 2 ... Kn and K i ~ sub(K) for each 1 ~i<~n. AMMEL 2.3. Let K, K 1 ..... Kn, n ~> ,1 be languages. (1) Let K= U7=1 Kr Then K is (strongly) repetitive if and only if there exists a 1 .< i ~ n such that K i is (strongly) repetitive. (2) Let K < (K1 ,..., Kn). Then K is (strongly) repetitive if and only if there exists a 1 ~< i .< n such that K i is (strongly) repetitive. Proof. Obvious. II AMMEL 2.4. Let G be a DOL system and let G' be its simplification. Then G is (strongly) repetitive if and only if G' is (strongly repetitive). REPETITION OF SUBWORDS 19 Proof. Follows immediately form the fact that one can homomorphically "translate" from G to G' and from G' to G. II 3. MAIN RESULTS In this section we state two main results of this paper and indicate the strategy of their proofs. The following two results are the main results of this paper. MEROEHT .1 It is decidable whether or not an arbitrary DOL system G is repetitive. MEROEHT 2. Every repetitive DOL system is strongly repetitive. In order to prove these results we will prove the following two (more technical) theorems. They allow us to concentrate on SDOL systems (rather than consider arbitrary DOL systems). MEROEHT 3. (1) It is decidable whether or not an arbitrary DOL system is repetitive if and only if it is decidable whether or not an arbitrary SDOL system is repetitive. (2) If every repetitive SDOL system is strongly repetitive, then every repetitive DOL system is strongly repetitive. MEROEHT 4. (1) It is decidable whether or not an arbitrary SDOL system is repetitive. (2) Every repetitive SDOL system is strongly repetitive. Clearly Theorems 3 and 4 together imply Theorems 1 and 2. Thus the rest of this paper is devoted to proofs of Theorems 3 and 4. In the next section we prove Theorem 3. In Section 5 we consider closed and strongly closed subalphabets of the alphabet of a SDOL system. Considerations of this section form important technical tools for Section 6 where Theorem 4 is proved. 4. PROOF FO THEOREM 3 In this section Theorem 3 is proved. MEROEHT 3. (i) /t is deeidable whether or not an arbitrary DOL system is repetitive if and only if it is decidable whether or not an arbitrary SDOL system is repetitive. 20 EHRENFEUCHT AND ROZENBERG (ii) If every repetitive SDOL system is strongly repetitive then every repetitive DOL system is strongly repetitive. Proof. (i) Clearly it suffices to prove the if part of the statement only. To this aim we proceed as follows. Let G = (22, h, co) be an arbitrary DOL system. First we decide whether or not G is finite (it is well known that finiteness is decidable for DOL systems). If G is finite then (see Lemma 2.2(2)) G is not repetitive and we are done. If G is infinite then (see Lemma 2.1(1)) we decide whether or not G is pushy. If it is, then (by Lemma 2.2(1)) G is strongly repetitive and we are done. Thus let us assume that G is not pushy. Let G c be the "coded version of G" defined as follows. G ~ = (L ,c" h ,~ 09c) where X ~ = {(a,x, fl):xE 2J-S o, a, fl~X* and lat, lfll <~ q(G)}, ~90 = (a,,y,, a~)(a2, y2, a,) ..- (at/_ 1,y,_1, at/) where 90 = alYla2y 2 ... an_lYt/_lan, Yi E Z -- Z 0 and aj ~ S*o for 1 <~ i <~ n -- 1 and 1 ~<j <~ n, for (a, x,/~) E X ,~ h C((a, x, fl)) -- (h(a) al, Yl, a2)(c~2, Y2, ~3) "'" (c~t/_l, Yt/-1, at/h(fl)) where h(x) = al y l a2 y 2 ... an_ l yt/_ l a . , Yi C ~, and aj E 22" for l <~ i <~ n - 1 and 1 ~<j <~ n. -- ,S O By Lemma 2.1 G c is effectively constructible. CLAIM 4.1. (1) G c is (strongly) repetitive if and only if G is (strongly) repetitive. (2) G c is strongly growing. Proof of Claim 4.1. (1) This follows directly from the following obvious observation. If E(G)= 90 0, 9o 1 .... and E(G ~) = 09g, 09~,..., then, for every m >/0, 09m---- alYl "'" an-lYn-lan REPETITION OF SUBWORDS 21 if and only if c=moc (al,yl,a2)(a2,y2, a3) ... (a, 1, y,,a,) whereyiCS-S 0andaJCS0* for l~<i~<n-1 and l~<j~<n. (2) Since G is not pushy, no letter outside S 0 has a rank. Conse- quently no letter in G c has a rank and so G c is strongly growing. II MIALC 4.2. There exists an algorithm which given a strongly growing DOL system H produces a finite set H 1 .... , H t, t ~> ,1 of DOL systems such that (1) H is (strongly) repetitive if and only if H i is (strongly) repetitive for some l ~< i ~< t, (2) H i is speeial for each I ~< i ~< t. Proof of Claim 4.2. Consider the algorithm A defined by the diagram of Fig. 2, where inputs are strongly growing DOL systems and the operations are defined as follows. SLICE Let H= (O,g,p) be a strongly growing DOL system. It is well known that, for each a C O, alph(g(a)), alph(g~(a)), alph(g3(a)) ..... is an ultimately periodic sequence; let Pa be a fixed positive integer which is a multiplicity of a period of this sequence and is bigger than a threshold of this sequence. Let, for each a E O, ra be a positive integer such that the sequence I gra(a)l, I g2r°(a)l,..., is a strictly growing sequence of positive integers; it is well known that such an r a exists. Let s be the least common multiple of all the integers p~, r~. Then SLICE(H) = {H0, H~ .... , Hs_ 1 ,} where H i = (O, g', g;(p)) for 0 <~ i ~ s -- .1 SPLIT Let H be a set of (strongly growing) DOL systems. Then SPLIT(H)= ~),~n SPLIT (H), where for H -- (O, g, p). SPLIT (g) = 1H{ ..... HIok} with ~H = (O, g, ai) for each 1 ~< i <~ IPl, where a i is the i'th letter of p. REMOVE UNACCESSIBLE (RU) Let H be a set of (strongly growing) DOL systems. Then RU(H)= UH~H RU(H), where for H= (O,g,p), RU(H)= (O,g,p), where O= ~)_.( i=0 alph(gi(p)) and ~ equals g restricted to O*. 22 EHRENFEUCHT AND ROZENBERG TUPNI I ECILS SPLIT EVOMER ELBISSECCANU YLETAMITLU YFILPMIS I TILPS OUTPUT ERUGIF 2 ULTIMATELY SIMPLIFY (US) Let H be a set of (strongly growing) DOL systems. Then US(H)= n~u)-.( US(H), where US(H) is an elementary version of H. It is easily seen that when A is given a strongly growing DOL system H, it produces a finite set H a,..., H t, t >/1, of DOL systems which are special. Hence (2) of the statement of the claim holds. Then part (1) of the statement follows directly from Lemmas 2.3 and 2.4. Now we complete the proof of Theorem 3(i) as follows. Let us consider the algorithm R given by the diagram of Fig. 3. Clearly, if it is decidable whether or not an arbitrary SDOL system is repetitive, then (from Claims 4.1 and 4.2 it follows that) the algorithm R decides whether or not an arbitrary DOL system is repetitive. Hence (i) holds.