Alberto Apostolico

Maxime Crochemore'

FAST PARALLEL LYNDON FACTORIZATION WITH APPLICATIONS

Keywords: parallel computation, combinatorics on words, string matching, Lyndon words. AMS subject classification: 68C25

It is shown that the Lyndon decomposition of a word of n symbols can be computed by an CReW PRAM in O(log n)

time. Extensions of the basic algorithm convey, within the same time and processors bOWlds, efficient parallel solutions to problems such as finding the lexicographically minimum or maximum suffix for aU prefixes of the input string, and finding the lexicographically least rotation of all prefixes of the input.

INTRODUCTION

Within the vast domain of sorting, a special role is played by problems defined in terms of lexicographic orders. Among problem.s in this class, we find that of sorting a set of strings over some ordered alphabet, finding the lexicographically least circular shift of a string, finding the lexicographically smallest or largest suffix for a string, etc. In the realm of serial computation, the last three problems are solved efficiently by resort to a special factorization of the free monoid [131 introduced in [START_REF] Chen | Free Differential Calculus, IV[END_REF] and known as Lyndon factorization (or decomposition). According to this factorization, any word can be decomposed wriquely into a sequence of lexicographically non increasing factors, with the additional property that each such factor is lexicographically least among its own circular shifts. Optimal, linear-time algorithms for the Lyndon factorization of a word were given in [START_REF] Duval | Factorizing Words over an Ordered. Alphabet[END_REF], along with the implied linear-time solutions for the related problems of finding lexicographically least circular shifts, computing minimum suffixes, etc. Recently, further properties of the Lyndon factorization were used to compute in optimal O(n 2 ) time the least rotations of all substrings of a string of n symbols [START_REF] Apostolico | Optimal Canonization of All Substrings of a String[END_REF].

A handful of algorithmic problems on strings [START_REF]Combinatorial on Words[END_REF] have been attacked to date also in the framework of parallel computation (see, e.g., [START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF], [START_REF] Apostolico | Parallel Construction of a Suffix Tree, with Applications[END_REF], [6], [START_REF] Crochemore | Usefulness of the Karp-Miller-Rosenberg Algorithm in Parallel Computations on Strings and Arrays[END_REF]). In this framework, one is usually interested in approaching optimum speed-up for a problem, in the sense that the product of the time taken by a parallel solution and the number of processors used should be as close as possible to the asymptotic complexity of the best serial algorithm available for that problem. Typically, the available efficient sequential algoritluns do not lend themselves to efficient parallelizatiollS, so that fast parallel algorithms are to be developed mostly from scratch. In particular, none of the parallel algorithms on words produced resembles any sequential predecessor. The algorithm presented in this paper is no exception to this rule. In this paper, we show that the Lyndon decomposition of a word of n symbols can be computed by an n-processors CRCW PRAM in O(log n) time and linear space. The best previous parallel solution to this problem uses a CRCW PRAM with n processors and takes O(log2 n) time with linear space, or O(logn) time with quadratic space [START_REF] Crochemore | Usefulness of the Karp-Miller-Rosenberg Algorithm in Parallel Computations on Strings and Arrays[END_REF]. Although the time x pToceS!JOTS bound of this paper does not achieve optimum speed-up, it is very close to the n(logn/loglogn) lower bound for computing such elementary flUletions as the parity of n bits on a CReW PRAM using a polynomial number of processors [START_REF] Beame | Optimal Bounds for Decision Problems on the CRCW PRAM[END_REF]. This paper is organized as follows. In the next section, we recall some basic known facts of combinatorics on words and lexicographic orderings. In Section 3, we analyze the robustness of the Lyndon decomposition of a word x under extension operations that change x into a new word Xl = xw, where w is an arbitrary word. In Section 4, we study more in detail the relation between the Lyndon factorizations of two given words x and Xl and the Lyndon decomposition of w = xx'. Some of the properties we derive are of independent interest. Section 5 contains the description of our parallel algorithm for the Lyndon decomposition of a word, based on the results of the previous sections. In the final section, we describe some applications and extensions of the main algorithm that lead to solve, in overall O(logn) time, some problems defined on the set of all prefixes of the input string. Specifically, we consider the problem of finding, for every prefix of the input, the lexicographically smallest or largest suffix, and the lexicographically least among all rotations of that prefix. The last application is based on some properties of Lyndon decompositions recently introduced in [START_REF] Apostolico | Optimal Canonization of All Substrings of a String[END_REF].

PRELIMINARIES

Let E be an alphabet totally ordered according to the relation <, E+ the free semigroup generated by E, and E* = E+ U {A}, where A is the empty word. The total order < is extended in its corresponding lexicographic order on E+1 as follows: For any pair of words x,y E E+, X < Y iff either y E xE+ or x = ras, y = rbt, with a < bj a, b E Ej r , s, tEE"'.

In the following, we write u « v or v u to denote that u < v but v is not in uE*.

Fact 1 . Let u -< v. Then, for any W , z in E*, we have uw -< vz.

A word x E E-is a Lyndon word iff x is strictly smaller that any of its proper suffixes. For example, a, b, aaab, abbb, aabab and aababaabb are Lyndon words on the alphabet E = a, b, but abab and abaab are not. By the definition of lexicographic order, one gets then immediately that if x is a Lyndon word, then no nonempty suffix of x can be also a prefix of x. A word with this property is border•free. A word x is primitive if setting x = w k implies k = 1. An immediate consequence of the preceding statement is then that any Lyndon word is a primitive word. A word x is strongly primitive or squarefree if every substring of x is a primitive word. For example, cabea and cababd are primitive words, but eabea is also strongly primitive, while cababd is not, due to the square abab. Fact 2. Let 1 be a Lyndon word, v E E+ a suffix of 1 and u a prefix of v. Then u < 1 implies that u is a prefix of l. In other words, u -< 1 is impossible.

The following central theorem holds [START_REF] Chen | Free Differential Calculus, IV[END_REF].

Theorem 1. Any word x E E+ may be written in a unique way as a nonincreasing product of Lyndon words: x = 1112 .. .lkl 1 1 1 2 2::: ... lk• Moreover, lk is the (lexicographically) smallest suffix of x.

The sequence (h,1 2 , ... j lk) of Lyndon words such that x = ZllZ ...lk and 11 :2:: 1 2 :;::: ... ;::: lk is called the Lyndon decomposition or Lyndon factorization of x. In the following, we refer to it simply as the decomposition or factorization of x. The following claim is an obvious consequence of the fact that 11 is the longest Lyndon word that is also a prefix of x.

Fact 3. Let 1 be a Lyndon word. For any wEE"', the first factor 11 in the decomposition of Iw obeys the condition 11,12: III.

The following notions will be needed in the sequel. If x = vwy, then the length Ivl of v is the position of w in x. Let 1112 ...h be the Lyndon decomposition of a string x.

For any t (t = 1,2, ... ,k -I), tail(lt) is the suffix of x having the same position in x as lHb i.e.) tail(lt) = It+lZt+2 ...1k. We also set tail(lk) = A, and, with the convention that 1 0 = >., tail(lo) = x. For any t(t = 1,2, ... ,k), rest(lt) is the suffix of x at position i + lId, where i is the position of the last factor identical to It in the decomposition of x. For example, for x = bbababa we have it = 1 2 = b, 1 3 = 1 4 = ab and 1 5 = a. We also have tail(l,) = bababa and Test(l,) = tai/(l,) = ababa. Finally, tail(l,) = aba, and tail(l.) = Test(l.) = Test(l,) = a.

FACTOR STABILITY UNDER RIGHT EXTENSIONS

In this section, we study the robustness of the factors in the decomposition of a word x with respect to arbitrary extensions of x into a new word xw. It is easily seen that the factorization of some such extensions are themselves easy extensions of the factorization of x, while others depart quite substantially from the factorization of x. For example, let x = abcababcababcab. Then, we have 1 1 = abc, 1 2 = 1 3 = ababc and 1 4 = abo Appending to x a string w consisting of the single symbol b leaves h, hand 1 3 unaltered, and only requires extending 1 4 into the new factor abb. If, on the other hand, we had chosen w = c, then the decomposition of xc would have 1 1 = abc and 1 2 = ababcababcabc, which is dramatically different from the decomposition of x.

We say that a factor I in the decomposition of a string x is right-stable if I is a factor of the decomposition of xw for any w E •. Let now 1],1 2 , ...,lk be the decomposition of x. Clearly, lk is never right stable unless lk coincides with the maximum symbol c in However, if lk = c and k > I, then it must be 11 = 1 2 = ... = h, and all factors are right-stable. Observe also that, for [hI> 1 the first symbol of Ii cannot be c. In the nontrivial case that lk is not c and that k > I, the following theorem characterizes the right-stable factors in the decomposition of x.

Theorem 2. Let 1 1 ,1 2 , ...,lk be the decomposition of x, and assume that k > 1 and lk =f:. c. For any t in [1, k -I], it is right-stable if and only if rest(lt) is not a prefix of it.

Proof. Assume that It is right-stable but rest(lt) is a prefix of It. We show that, in this case, It is not a factor in the decomposition of xc. By the definition of rest(lt), we have that w = tail(lt_d = (It)!resi(lt) for some integer f ;::: 1. We show that we is a Lyndon word. Thus, even if a factor of the decomposition of xc started with 1 t1 It would only be a proper prefix of such a factor. Choose i such that Irest(lt)cil = 11 t l + 1. Let z be an arbitrary suffix of I tl and u be the suffix of of resi(lt)c i -1 such that lui = Izi. [START_REF] Duval | Factorizing Words over an Ordered. Alphabet[END_REF] that a < a' implies that ItIt+l ...va' is a Lyndon word. Hence, a < a' is impossible in our case, since it would violate Fact 3. It is convenient to carry out this part of the proof explicitly, both for completeness of presentation and for future reference. Recall that, since it is a Lyndon word, then for every suffix z of it, we have z::»-it and, by Fact 1, z(I t )9 va' ::»-(It)fva', where f was defined earlier in this proof and 9 < f is a natural number. Thus, we only need to show that for every suffix z of va', it is also z::»-ItIt+l ...va'. This is obvious for z = va', due to the hypothesis that va is a prefix of It and a < a'. Let then z be an arbitrary proper suffix of va', and write z = zla l . Since v is a prefix of III then clearly z' « it is impossible, by Fact 2. Hence z' < It implies that z' is a prefix of It. Thus, there exist a" in E such that z'a ll is a prefix of It. But va is also prefix of It, and z' is a suffix of v. Therefore, it must be a 2:: a", by Fact 2. Hence, a' > a yields a' > a" and

z = z'a'» z'a ll
, that is, z Itva'. In conclusion, assuming a' > a yields that ltva' is a

Lyndon word. This violates Fact 3. Thus, since a f:. a', it must be that a > a', whence the claim is established for it not a prefix of rest(It}.

We now show that It cannot be a prefix of rest(i t ). In fact, let 9 > aand u be chosen, respectively, as the maximum integer and the longest prefix of it for which (It)9 U is a prefix of rest(lt). Clearly, rest{lt) = (It)9u is impossible, for otherwise every factor following it in the decomposition of x except u would be identical to It, and we would have rest(lt) = u and u a prefix of It, in contradiction with our assumptions. Thus, there are symbols a and a' such that a =1= a', (It)gua' is a prefix of rest(I t ) and ua is a prefix of It. Assuming a > a' yields that the first 9 factors in the decomposition of rest(lt) are each identical to It, which contradicts the definition of rest(lt). Assuming a < a' implies instead, through an argument already used earlier in this proof, that ltlt+l ...ua' is a Lyndon word, which contradicts the assumption that It is a factor in the decomposition. Hence, It cannot be a prefix of rest(lt). 0

COMBINATORICS OF COMPOSITIONS

In this section, we study how the decompositions of two strings x and x' are related to the decomposition of string xx'. This is easy in the case where both x and x' are Lyndon words, in view of the following known fact (cf., e.g., [START_REF] Duval | Factorizing Words over an Ordered. Alphabet[END_REF]).

Fact 4. Let u and v be Lyndon words. Then uv is a Lyndon word if and only if u < v.

In general, the composition of two factorizations is less straightforward. Of course, right-stable factors of x are not affected by the extension of x into xx', but we know that in the general case at least one factor is not

We start by listing two lemmas that shall be of use later.

Lemma 1. Let I and I' be two distinct Lyndon words such that, for some u E E+ and vEE"', we have that I' = uv, and u is a suffix of l. Then, Iv is a Lyndon word.

Proof. The assertion trivially holds if v is empty, thus we assume henceforth that v is not empty. Since I is a Lyndon word, then for any suffix u' of I we have u' » I, whence, by Fact 1, also u'v Iv. Letting now v' be v or some suffix of v we have also v'

I' > u l,
which concludes the proof. • Lemma 2. For u E E+ and vEE"', let [ = uv be a Lyndon word. Then, for any wEE"',

Ivl is the position of a factor in the decomposition of vlw.

Proof. Let [' be the last factor in the decomposition of v. Then, [' is border-free. Let u be the longest prefix common to 1/ and l. Since I is a Lyndon word, we have luj < WI, whence there are symbols a and a' such that ua' is a prefix of I' and ua is a prefix of I.

Now at < a is impossible, since it violates Fact 2. Hence, it must be a > a', i.e., [/ is right stable in vI. The rest of the claim is an immediate consequence of Fact 3. • From now on and until stated otherwise, ... is the factorization of a nonempty string x'. Consider the string xx', where x has factorization h[2 ...h, and let d be the minimum index in the decomposition of x for which factor Id is not right-stable. From now Oll, when referring to a string Z, we use z as a subscript of rest and tail. Let f 2:: 1 be the integer value for which tail z (ld_d = (ld)'resi:l:(ld). For an arbitrarily large m, let y be the longest prefix COllUDOD to (ld)m and rest:r;(ld)X'. We have, by Theorem 2, that Iy] 2:: Irestx(ld)l• Clearly, ld is either a factor or the proper prefix of a factor in the decomposition of xx/.

Lemma 3. Asswne that IYI < 211dl, and let 9 be the largest index for which s = ... is a prefix of (ld?' Then one of the following cases applies: Case 1: each one of the consecutive occurrences of Id in tailzUd_dx' is a factor in the decomposition of XXi; moreover, each such occurrence is right-stable in xx' iff y =I=restx(ld)X'.

Case 2: the word z = ... = (ld)f is a Lyndon word.

Before starting with the proof, we observe that, since all the Ii'S with i < dare rightstable, then, in the light of Fact 3, we get that in Case 2 z is a factor or the prefix of a factor in the decomposition of xx'.

Proof. The assertion holds if we have y = rest:r;(ld)X', since in this case the suffix of XXi at position 11l1z ... ld_ll is in the form (ld)il with f $ i $ f + 1 and I = ld or I is a proper prefix of ld. Hence, Case 1 of the claim applies, since ld is a Lyndon word. Clearly, the occurrences of ld in such a suffix are not right-stable factors for xx'.

Asswne henceforth y =F rest:r;(ld)X'. We have the following alternatives.

(A) lyl =F 11dl• This case encompasses two subcases depending on whether (subcase AI) Iyl < Iidl or (subcase A2) Iidl < Iyl < 211 d l. Clearly, there exist two distinct symbols a and a ' such that a' is a symbol of ya is a prefix of ld' and either (subcase AI) va' is a prefix of rest:r;(ld)x', or (subcase A2) ldya' is a prefix ofrest:r;(ld)x'.

Irrespective of which subcase applies, if a > a', then we have Case I, with every consecutive factor identical to ld being also right-stable in xx'. For a < ai, we have that a prefix of tail:r;(ld_dx l is either in the fonn w = (ld)fya l (Iyl < Ild!), or in the form ]x'i or p IS the position of a Proof. The claim holds trivially for p = Ix'l, so that we concentrate on the case p < Ix'i.

w = (ld)f+ 1 ya' (lid I < Iyl < 211dl) In
Assume first Iy] = Iidl and let a and a' be defined as in alternative B of Lemma 3. Since ld is a factor in the decomposition of xx'1 then Case 2 of Lemma 3 cannot apply, and we have a > a'. Assume that a/ is not the first symbol of Then there is a nonempty word u such that u is a prefix of and also a suffix of [do Let al/ be the first symbol of u. Since is a Lyndon word, we must have a f all. But then also a > a" I contradicting the assumption that Id is a Lyndon word.

Let now Iyl > IIdl, and assume that p is not the position of a factor in the decomposition of x'. Then, there is a factor I' in such a decomposition such that I' = u'v' with u' nonempty and u' a suffix of I d . But then Lemma 1 ensures that {ld)f+ 1 V ' is a Lyndon word, and thus a factor or the prefix of a factor in the decomposition of xx'. This contradicts the assumption that I d is the d-th factor in such a decomposition. • Lemma 5. Assume IYI ?: 21Idl, i.e., (ld)2 is a prefix of rest2;(ld)X ' , and that Ii = Id is a factor in the decomposition of x', but =f:. I d for i < j. Let t be the largest integer for which {ld)t is a prefix of taiI2;(I d _x)x'. Then, every occurrence of I d in this prefix of taiI2;(I d _ 1 )x' is a factor in the decomposition of xx'.

Proof. Since I d is border-free, then Ii must coincide with the second occurrence of I d in restz(ld)X I • Let g be the largest integer and u E E'" the longest prefix of ld such that (Id)9 U is a prefix of restx(I d )x ' . Since Ii is a factor in the decomposition of x', then either = (ld)t-2u or else = (ld)9-2 uav for some a E E and vEE'" such that ua « Ii = I d • The assertion clearly holds in both cases. (Note that, in the second case, every occurrence of ld is right-stable in XXi.) • Lemma 6. Assume that (ld)2 is a prefix of rest(Id)x'. Let Ii be defined as in Lemma 5, but assume that Ii is not a factor in the decomposition of x'. Then there is a nonempty prefix v of x' such that tail.(ld_l)V is a Lyndon word and Ivl ! Ix'i implies that Ivl is the position of a factor in the decomposition of x'.

Proof. We know from Lemma 2 and Fact 3 that Ii must be the prefix of a factor in the decomposition of x'. Let y be this factor. Since both L d and yare Lyndon words and I d < y, then repeated application of Fact 4 yields that (ld)iy is also a Lyndon word for any i?: 1. Obviously, ... Ii_lyl is the position of a factor in the decomposition of x'. This establishes the claim. • We say that the two strings x and x' have a simple composition if x is a Lyndon word.

In the following theorem, we make the convention that lk+l = 1 0 = >.. In informal terms, the theorem shows that the factorization of XXi can be always split into two segments with the following properties. The first segment is simply a prefix of the factorization of x.

The second segment is the solution to a problem of simple composition that involves an identifiable Lyndon word and a suffix fe of x' such that the factorization of x' is a suffix of the factorization of x'. Proof. Let d ::; k be the smallest index for which la is not right stable in x. We distinguish the following cases.

Case ld = lk•

The claim holds trivially if x' is of the form (ld)C u , with u a prefix of ld = lk and c ;::: o.

Asswne next that, for some c ;::: 0 and distinct symbols a and a', we have that (ldYua is a prefix of tail:e(ld_l)X' = (ld)k-d+l x ' and (ldYua' is a prefix of (ld)k-d x '. If a> a', then we know that each one of the consecutive c + 1 occurrences of ld in tail:e(ld_l):X' is a factor (in fact, a right-stable factor) in the decomposition of xx' l and that is the first factor in the decomposition of u.

Setting then i = d -1, i' = m = c -k + d and
1= ld clearly meets the claim. If a < a', then w = (ldy+1ua' is a Lyndon word, and we know from the preceding lemmas that w is also the prefix of a Lyndon word z such that

Izi -(k -d + 1)11dl is either Ixll or the position of a factor in the decomposition of x'.

Clearly, setting i = d -1, 1= z, m = 1 and i' = t satisfies the claim.

Case ld "Ilk.

By Theorem 2 and the definition of rest, we have that restz(ld) is a proper prefix of ld. Since Id =f:. lk, we also have that restz(ld) =f:. A. Assume first that the condition of Lemma 3 is satisfied and results in an instance of Case 2. Then, taking i = d -1, [ = z and i' = 9 + 2, where z and 9 are defined in that lemma, clearly meets the claim. The claim is easily met for each one of the cases considered in Lemmas 4-6, i.e., in all cases where Ld = restz(ld)v with v a prefix of x'. In brief, this is due to the fact that in all these cases there is one occurrence of ld which originates in x and terminates in x'. Then, either L d is a factor in the decomposition of xx' and we choose I = L d (Lemmas 2 and 4 guarantee then the existence of i' as specified in the claim), or else Id is the prefix of a Lyndon word that originates in x and ends in x' (then Lemma 6 guarantees the existence of i').

We are left now with the instances of d < k where Case 1 of Lemma 3 occurs. The existence of i' is no longer guaranteed for the choice 1= [do However, we know that under these conditions Id and every subsequent replica of it are right-stable factors in xx'. Let It be the first factor in the decomposition of restz(ld). If It = lkl then we have seen that it is possible to satisfy the claim. If It =f:. lk' then rest:z;(ld) is not border-free. It is also easily seen that, for It ::f I kl It cannot be right-stable (since rest:r;(ld) is a prefix of Id' then imposing that It be right-stable would violate Fact 2 for Id). In summary, for It =f Ik we have that it is not right stable, and there is an integer c 1 such that = (It)Crestz(lt), with restz(lt) a nonempty prefix of It. Applying to It the case analysis previously developed for I d either satisfies the claim or else yields that the c replicas of it in x are right-stable.

Repeated application of this treatment yields the claim. •

Assume now that we are given a Lyndon word 1 and the decomposition h,l'l, ... , h of some string x. At this point, we are interested in the relation between the decomposition of x and the decomposition I]I 2 ...lr. of Ix. This is the case where we say that 1 and x admit of a simple composition, which seems to imply that the structure of the decomposition of Ix is related in some trivial way to the structures of 1 and of the decomposition of x. This is not always the case. In fact, appending just one symbol to the left of some string x may upset the entire decomposition of x. For example, let x = ebebbebebbcbeabbe. We have h = e, h = be,1 3 = 1 4 = bbebe,i s = abbe. If we append an a to the left of x, we get, for ax, that I] = aebebbebebbebe and 1' 1. = abbe. The following is an easy consequence of lemmas 5 and 6. Lemma 7. Assume that Lyndon word 1 is a prefix of x. Then either II = 1, or else II = Ih.

Proof. That only one of the cases in the claim may apply follows from Fact 3. The rest of the claim is an easy corollary of lemmas 5 and 6. • Theorem 4. Let t be the smallest index m the decomposition of x such that w

11 1 i 2 •••1 t _ 1 2:: It• Then, II = wand 1 2 = it•
Proof. By our choice of t, we have that, for every d < t, IhI2 ... ld < i d + 1 • But then, using Fact 4, it is easy to establish by induction on d that that 11 1 i 2 ...1 d is a Lyndon word for d ::; t. The assertion then follows from Lerruna 7 in case of equality between wand It.

Assume henceforth it < w. The assertion is obvious if II « w, thus we assume henceforth that It is a prefix of w. Let u be the longest common prefix of w and The claim holds clearly when u = Ittai12:(lt). Assuming then u =f:. lttailx(lt), there are distinct symbols a and a' such that ua is a prefix of wand ua ' is a prefix of lttail:r:(lt). We show that a < a' is impossible, thus establishing the claim also in this case. Since u is a prefix of a Lyndon word, then u can be written as (vax )m v for some integer m and Lyndon word vax. If a > a/, then ua' = (vax )rn va l is also Lyndon word. But It is a proper prefix of ua', which contradicts Fact 3. •

ALGORITHMIC IMPLEMENTATION

In this section, we use the results developed earlier in the paper to design a CROW PRAM algorithm for computing the Lyndon factorization of an input word s of Is I = n symbols.

We assume to be given n processors PbP2, "'lPn, that have simultaneous, random access to a memory bank consisting of OCn . T) locations, where T is the total time taken by our computation. We say that processor Pi (i = 1, 2, ... , n) has serial number i. The input is stored into an array of consecutive locations of the conunon memory, and processor Pi is assigned to the i-th symbol of s (i = 1,2, ... ,n). Any subset of the n processors can concurrently read from or write to the same memory location. When more than one processor attempts to write, we make the convention that the one with the smallest serial number succeeds. This variant of the model is called PRlORITY CRCW. In our application, this type of concurrent write can be simulated in constant time [START_REF] Fich | Relations between Concurrent-write Models of Parallel Computation[END_REF] by the weaker model where one processor at random succeeds in writing but it is not know in advance which one will succeed.

We adopt a standard divide-and-conquer scheme, consisting of log n stages each requiring constant time. Assuming w.l.o.g. that n is a power of 2, we regard the positions of the input string at the beginning of the S-th stage as partitioned into n/2 5 -1 disjoint bloch! each of size 2 5 -1 . Starting with the first block [1,2 5 -1 ], we give all blocks consecutive ordinal numbers. For S = 1,2, ... ,logn, stage S handles simultaneously and independently every pair formed by an odd-numbered block B and by the even-numbered successor B' of B. For every such pair, the goal of the stage is that of combining the already computed factorizations of the two substrings x and x' of s that are stored, respectively, into Band B' into the factorization of xx'. Thus, the main invariant is that at the beginning of stage S the factorization of every block of size 2 5 -1 has been computed. We call this Invariant o. Invariant 0 trivially holds for S = 1, since the factorization of a single symbol is the symbol itself.

We only need to show how two blocks such as Band B' are combined. We apply to the two associated strings x and x' the notational conventions made in connection with Theorem 3. We need a few additonal notions, that are given next.

The first position of each block of s is called the block head, and the processor assigned to the head of a block is the block representative of that block. Since the block partitions are rigidly defined for each stage, then the position of any block head can be computed by any processor in constant time. Similaxly, if 1 is a factor in the decomposition, say, of X, then the first position of I is the head of that factor, and the processor assigned to the first symbol of I is the factor representative of I. With respect to the decomposition of either x or X ' , an I-run is a maximal sequence of factors identical to I in such a decomposition. The total number of replicas of 1 in the l-run is the size of that run. For every run, the factor of the run having minimum index in its associated decomposition is called the head of that run; the representative of that factor is also the run representative of that run. Our scheme will maintain, in addition to Invariant 0, the following auxiliary invariants.

Invariant 1. If processor p is assigned to a position of factor [ in the decomposition of x (respectively, x'), then p knows the address in B (resp., B') of the head of I as well as the address (or serial number) of the representative of the run containing I.

Invariant 2. The representative of an [-run knows III and the size of that run.

The following three steps have the effect of combining the decompositions of x and x' into the decomposition of xx'. The first two steps take place only if x and x' do not have a simple composition. The combination of a single Lyndon word with the decomposition of a given string is instead the task of the third step. The condition that the factorization of x contains only one factor is easily checked in constant time, e.g., using two consecutive appropriate concurrent writes to the block head of B to see whether there are two distinct factor representatives. Henceforth, we assume that there are at least two factors in the decomposition of x. In the course of our description, we will say often that our scheme identifies or handles the indez (i.e., ordinal number) of a factor in the decomposition of either x or x'. This phraseology is used only in order to relate in a clearer way to the results of the previous section. It should be understood that, in actuality, the scheme only identifies and handles the heads of the factors having the said indices. This distinction is important, since our time bound would not be achieved if an explicit computation of factor indices had to take place at each stage.

Step 1. The goal of Step 1 is to detect the factors of x that are not right-stable. Theorem 2 is the handle for this. For every factor y of x, the representative of the y-run computes, using Invariant 2, the position of restx(Y) in B. If jrestx(y)1 > Iyl, then (every factor in the y-run is right-stable) the run representative simply sets an appropriate flag in the first position of the run head. If, on the other hand, Irestx(y)1 ::; Iyj, then the Iyl processors assigned to the head of the run inspect the first Iyl symbols of restx(Y)x'.

Specifically, the processor assigned to the d-th symbol of y (d = 1,2, ... lyl) checks whether that symbol matches the d-th symbol of restz(Y)x'. Note that this processor can actually compute the value d using Invariant 1. Subsequently, all processors detecting a mismatch attempt to write their respective serial numbers into a memory cell uniquely associated with the representative of the run. In OUI working model, the processor having smallest index succeeds. The representative of the run can now check in constant time whether the right-stability condition of Theorem 2 is satisfied, in which case it sets the :flag located in the first position of the the nrn head. Using Invariant 1 again, every processor of block B can learn at this point by inspection of the appropriate flag whether the factor it is assigned to is right-stable or not. The processors assigned to right-stable factors will remain idle for the remainder of the stage. All others (recall that there is always at least one non right-stable factor) proceed to Step 2.

Step 2. The main goal of this step is to identify i, il,l, m and the position in x' of if', as per Theorem 3. If 1 and its possible subsequent replicas are found to be factors in the decomposition of xx', then such a decomposition will also be computed in Step 2, whence Step 2 will be terminal for the stage. If this is not the case, then Theorem 3 tells us that m = 1 and I and x' have a simple composition. In conclusion, if Step 2 is not terminal for the stage, we will only have to solve a well defined problem of simple composition, and this problem will be handled in Step 3. The details of Step 2 cannot consist of a mere recapitulation of the criterion set forth in Theorem 3. In fact, we are only allowed. constant time for the stage, which forbids pursuing the cascaded tests in that theorem. Our approach will be instead to exploit the constant time min computation inherent to our working model in order to reach quickly the bottom of the iterated argument subtending Theorem 3. From that point on, our main concern will be to show how the n processors can exchange information efficiently and carry out the rest of the work in constant time.

The opening action of Step 2 is the following test: for each nm of non-right-stable factors in the decomposition of x, the processors assigned to the head ld of the rtm test simultaneously and in constant time whether ld < restx(ld)X'. The details of this test are similar to those of Step 1. If no run head passes the test, then by Theorem 3 every factor in the decomposition of x is right stable in xx'. (The condition ld = restx(ld)X' is impossible at this point, since we ruled out that x is a Lyndon word.) Hence, the decomposition of XXi consists simply of the concatenation of the decomposition of x and that of x'. The operation of the stage is complete, since Invariant 0 holds now for xx' and invariants 1 and 2 are trivially propagated to next stage. Assume, on the other hand, that at least one run head passes the test. In this case, all run representatives passing the test use common-write to the block head in order to identify, in constant time, the successful run head having smallest index in the decomposition of

x. Let It be the winning run head. By Theorem 3, every factor preceding It in the decomposition of x is now right-stable in XXi, while It is either a factor or the prefix of a factor in the decomposition of xx'. The remainder of the stage takes one of two possible avenues, according to whether or not the condition resi;c(lt) = ,\ is satisfied.

Alternative 1: rest:z:(lt) =..\. This splits into two subcases according to whether or not It is a prefix of resi;c(lt)x'.

Assume first that It is a prefix of x'. Then (cf. Fact 3) It either is identical to or is the prefix of the first factor in the decomposition of Xl. Which case applies can be learned by inspecting the factor representative of factor 1 which is also the run representative of the in the decomposition of x'. If is identical to It, then must surrender its status of run head to the head of the It-run. Each one of the factor representatives of a factor formerly in the run learns about this change by inspection of their old run representative, and updates its knowledge of the run representative accordingly. This preserves invariants 1 and 2. Having accomplished the decomposition of xx' the stage tenninates. If > lit!, then It and all its subsequent replicas in x must coalesce with into a single Lyndon word.

In the most general case, will be the head of a run of size larger than 1. Before combining with tail:E:(lt-d, must pass its leadership on to the second factor in this -run. This is easily accomplished in constant time, due to invariants 1 and 2. The processors now assemble the Lyndon word z = (cf. Case 2 of Lemma 3) and enter Step 3 with i = t -1, m = I,l = z and i' the index of the first factor following in x'.

Asswne now that it is not a prefix of x'. We need to explain how the word z (that will serve as the parameter I to be passed on to Step 3) is computed. With the notation of Lemma 3, the main problem is that of identifying Let ya' be the shortest prefix of re.9t(lt)x ' that is not a prefix of It. The It-run representative p identifies the factor head of the factor of x' containing a' (this factor is called in Lemma 3). Processor p achieves this simply by inspecting the information about the factor head stored in the processor assigned to a'. At an extra constant time, p can also identify the run head of the containing Again, or its run-representative may have to surrender the status of run-representative to the successor of if = and this is done as earlier using the invariants. Once this is done, the lrrun representative can assemble word z of Lemma 3, using its own information and that stored in the old head of the Every processor assigned to a position of z updates its pointers to both faetor-and run representative, so that both point now to the old run representative of the it-run. The procedure now enters Step 3 with i = t -1, i' = 9 + 2, [= z and m = 1.

Alterna.tille 2: restx(lt) # >... This case splits into two subcases depending on whether or not (It)2 is a prefix of rest:z;(lt)x'. In the following, we use v to denote the prefix of x' of length 11,1-IrestxU,)I• Assume first that (It)2 is a prefix of rC8t:z;(lt)X'. Then Lemma 2 guarantees that Ivl is the position of a factor in the decomposition of x'. In other words, the decomposition of the suffix x' of x' that is obtained by deleting the first Ivl symbols of x' is a suffix of the decomposition of x'. Consider now the word xv. Clearly, the decomposition of xv can be obtained by that of x by first deleting all factors in the decomposition of resiz(lt) and then appending a new factor identical to I tl i.e., the factor contributed by the Lyndon word rest:z;(lt)v. At this point, the problem of composing the decompositions of xv and

x' is identical to the problem handled in the first subcase of Alternative 1. In the light of the preceding discussion, the manipulations that lead the processors to extend the decomposition of x into that of xv, and truncate x' into x', are trivial and are omitted.

Finally, assume that (1t)2 is not a prefix of rest x (1t)x'. If Ivl is the starting position of a factor in the decomposition of x', then this is similar to the subcase of Alternative 2 that was just discussed. Observe that, under our current assumptions, if it is to stay as a factor in the decomposition of xx' then lvl is guaranteed to be the position of a factor in the decomposition of Xl, by virtue of Lemma 4. All other cases of Alternative 2 are similar to the second subcase of Alternative 1.

Step 3. If Step 3 is entered, then we have identified a prefix x of x such that the decomposition of x is a prefix of the decomposition of x and also a prefix of the decomposition of xx'. We also have a Lyndon word z and a suffix x' of Xl such that we know the decomposition of x' and we know that XXi = xzx'. Thus, solving the problem of simple composition for z and x' is all is needed to complete the stage. This concludes the description of our scheme. The discussion of this section establishes the following result. Theorem 5. The Lyndon decomposition of a word of n symbols can be computed by a CReW PRAM with n processors in time O(logn) and linear space.

APPLICATIONS

1 -The minimum suffix of all prejixe8 of a string.

The most immediate application of the parallel algorithm of Section 5 is to the computation of the minimum suffix of the input string. In fact, the minimum suffix of a string is precisely the last factor in the Lyndon decomposition of that string [START_REF] Duval | Factorizing Words over an Ordered. Alphabet[END_REF]. Just as it happens for its serial predecessor [START_REF] Duval | Factorizing Words over an Ordered. Alphabet[END_REF], some light upgrades of our algorithm lead to actually compute the minimum suffix for every prefix of the string, leaving time and processor bounds unaltered. (We note, incidentally, that computing the minimum suffixes of all prefixes of a string yields an implicit description of the Lyndon decompositions of all such prefixes.)

To start the discussion of our method, we single out in Fact 5 below a useful characterization due to Duval [START_REF] Duval | Factorizing Words over an Ordered. Alphabet[END_REF] of the class P of all words that are nonempty prefixes of Lyndon words. A proof of Fact 5 is also pespersed in the proof of Theorem 2. Let S be the set of all words in the form (uv)k u , where u E E*, v E E+, k 1 and uv is a Lyndon word.

Fact 5. 'P = S if the alphabet E is unbounded, and 'P = S -{cklk 2}, where c is the maximum symbol in E, otherwise.

We assume familiarity of the reader with the notion of period of a string. We say that a period q of a word w is nontrivial if q =1= Iwl. Lemma 8. Let w be a word in 'P, and set p = 0 if w is unbordered, and p equal to the maximum nontrivial period of w otherwise. Then p is the position in w of the last factor in the Lyndon decomposition of w.

Proof. By Fact 5, we can write w in the form (uv)ku , where u E E•, V E E+, uv is a Lyndon word, and either u is not empty and k 1 and or u is empty and k > 1. If u is empty, then the decomposition of w consists of k factors all identical to uv, and the position of the last factor is (k -l)luv[. We also have p = (k -l)luv[, since uv is unbordered. For u not empty, kluvj is a nontrivial period of w. The claim thus holds if p = kluvl. If, on the other hand, p =1= kluv[, then it must be p > kluvl, i.e., u is bordered. Since u E 'P, we can apply to U the analysis previously applied to uv. Iteration of this argument yields the claim. • Let 1112 ...h be the decomposition of some word x. Combined with Fact 3, Lemma 8 shows that the minimum suffixes of all prefixes of x can be obtained by computing the minimum suffixes of all prefixes of each individual factor in the decomposition of x. From now on, we can therefore assume that the Lyndon decomposition at the outset of the algorithm of the previous section is given, and concentrate on a single factor 1 in such a decomposition. The understanding is that the manipulations performed on I take place synchronously on all other factors of the decompositiOD of x.

In view of Lemma 8, it is not surprising that III processors can compute all mimimum suffixes of Lyndon word I in O(log Ill) time, due to the strong relationship between this problem and plain string searching. Specifically, consider the table reach/ such that reachl[i] equals the maximwn length of a prefix of 1 that occurs also at position i (i = 0,1,2, ... , Ill-I). Given an integerk i, we say that the i-thsymbol of 1is dominated by reachdk], iff k + reach[k] i. For i = 1,2, ..., III, define now clo.e,!i] as the largest k such that reachdk] dominates l [i]. At this point, the criterion of Lemma 8 translates into saying that, for every prefix 1[1]1 [START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF] .. .l[iJ of 1, the position in 1 of the minimum suffix of

I[I]1[2] .. .1[i] is closerIi]. It is not difficult to compute
either one of the tables reach1or closel with 111 processors in O(log 111) time, e.g., by adaptation of the string searching algorithm in [START_REF] Galil | Optimal Parallel Algorithms for String Matching[END_REF]. Thus, given the Lyndon decomposition of a string x, the minimum suffixes of all prefixes of x can be computed by a CReW PRAM with n processors in O(logn) time and linear space. £ -The maximum su.Jji:z;es of a.ll prefize3 of a 3tring.

As pointed out in [START_REF] Duval | Factorizing Words over an Ordered. Alphabet[END_REF], this problem is not symmetric to the previous one. However, it is known that the lexicographically maximum suffix of a string x with respect to the converse of the order relation "<" is the longest one among the suffixes of x that belong also to the set S defined earlier. We will use a re-statement of this property to compute the maximum suffixes of all prefixes of x in log n CRCW steps, with n processors.

Let 1 be a factor in the decomposition of x and i the position of 1 in x. We say that an integer j is covered by 1 if either (j -i) s: 111 or restZ'[l]Z' [START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF] ...Z'U](I) = tail x [l)X [START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF] ...Z'(jJ(l) and rest x [l]x[2) ... x(jj(1) is a prefix of 1. Let C be the set of all factors covering j, and Im(j) the element of C having minimum index in the decomposition of x. The following property yields a criterion for finding all maximum suffixes of x. Fact 6. The position in x of the maximum suffix of x[1]x [START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF] ... x[j] equals the position in x of the run head of the Im(j)-run.

We refer to [START_REF] Duval | Factorizing Words over an Ordered. Alphabet[END_REF] for a justification of Fact 6. Given the Lyndon decomposition of x in the format specified in Section 5, it is easy to compute, for all j's, the positions of Im(j) and its run head, using n processors and log n steps. To avoid many tedious details, we describe the method informally. Let l(lJ(j), I(2J(j), ... , I(hl(j) be the factors of x covering j. For any d in [1, hJ, aligning factor I(dl(j) with tailz(l(dl(j)) will bring onto position j precisely one among the processors assigned to l(d)(j). Note that, for any j, there is a group of processors uniquely assigned to j in this way. Clearly, all processors assigned to j can perform a binary search driven by the length of x to identify the minimum among their own serial numbers. The j-th position of an array, serving as the target for common writes, can be used to perfonn the binary search. Having fOWld the minimum, invariants 1-2 lead to the identification of lm[j] and, from there, to the head of the lm(j)-run. 9 -The lexicographically least rotations of all prejizes of a string.

Given a word x = x[l]x [START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF] x[n], the i-th rotation of x (i = 1,2, ... ,n) is the string w

= x[i]x[i+ 1] ...x[n] x[l] x[2] xli -1].
A least lexicographic rotation (llr) of string x is a rotation of x that is lexicographically smallest among all rotations of x. Since all rotations of x have equal length, then for any two such rotations wand w', w :f w' implies that w and w' differ in at least one symbol. An llr of x is completely identified by its starting position (mod. [xl) in xx. We call such a position a least starting position (lsp). An lsp of x can be computed in linear time by serial computation. The fastest solution known was given in [14]. As pointed out in [10], the Lyndon decomposition of word xx will also expose an llr of x. This is due to the fact that the llr of x is either a Lyndon word or a power of a Lyndon word, and either case manifests itself while decomposing xx.

It is not difficult to compute the least rotation of x on a CRCW PRAM with n processors in O(logn) time. One possible approach is to perform, on xx, logn constanttime iterations of the following kind: At the i-th iteration, x is partitioned into n/2 i blocks of size 2 i , and, for each block, we know the starting position of a lexicographic minimum among all substrings of length 2 i + 1 of x originating in that block. The iteration consists of combining pairwise the blocks and computing one minimum substring of size 2 i + 2 for each combined block. We clearly have enough processors to perform all substring comparisons in constant time. The only difficulty is when both candidate substrings from two combining blocks extend into identical minima. Using an observation already in [START_REF] Shiloach | Fast Canonization of Circular Strings[END_REF], however, it is possible to always rule out one of the candidates in constant time, whence the overall computation is done in time O(log n).

Computing the llr's of all prefixes of x within the same bounds is more involved. For this task, we resort to a criterion recently established in [START_REF] Apostolico | Optimal Canonization of All Substrings of a String[END_REF], and used to compute the llr of all prefixes of x in overall linear time. Let 1 be one of the factors in the Lyndon decomposition of x. Define prev(l) as the prefix of x that precedes the first occurrence of 1. We say that 1is a special factor of x if and only if rest(l) is a prefix of 1and, in addition, one of the following conditions is satisfied:

-rest(l) is emptYi -I is a prefix of rest(l)prev(l); or -I < rest(l)prev(l) but I is not a prefix of rest(l)prev(l) .

Observe that, for any word x, the Lyndon decomposition 11121k of x has at least one special factor, namely, lk' As shown in [31, the following fact holds. Iprev(l,)1 is an lsp for x.

To see how Fact 7 can be used in our computation, assume that the table reach;c has been computed. (Recall that the n processors can compute reach;c in O(logn) time.) Consider now an integer j :$ Ixl = n, and let as earlier ImU) be the factor in the decomposition of x such that j is covered by lm(j) and m is minimum. Let i be the position of lm{j) in x and assume for generality that Ui) > IlmU)1 (i.e., j does not fall inside ImU)). It is not difficult to show that ImU) is a factor also in the decomposition of x[l]x [START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF] ...x [j]. Once reach x and the position i of lm(i) in x are available, it takes constant time for processor Pi to test whether lm{j) (whence also the run head of the lm(j)-run) is a special factor in the decomposition of x[l]x [START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF] ...x[j): This processor simply checks on reach:z; whether j -Ilm(j)1 is the starting position of a sufficiently long or (lexicographically) sufficiently small prefix of x. If the run head of the ImU)-run is a special factor for x[1]x [START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF]

  either snhcase, w is a Lyndon word. Case 2 of the claim then follows by applying Lemma 1 to the Lyndon words w and (B) Iyl = Ildl• This is similar to the previous alternative: we have now a =F ai, where a is the first symbol of ld and a ' is a symbol of Clearly, a < a ' yields Case 2, while a > a ' yields Case 1, with every factor right-stable in xx'. • Lemma 4. Assume that Iyl > lldl, and that llllz, ...,ld are the first d factors in the decomposition of xx'. Then either p = Ildl-Irestx(ld)1 factor in the decomposition of x'.

TheorelD 3 .

 3 Assume that x and x' do not have a simple composition. Then, there are always integers m and i', with m > 0 and 1 ::; if :S k' + 1, and a nonempty Lyndon word 1 such that we can write xx' = xx', with x = loll12 .. .lj(l)m, x' = Ij.li'+l ..

  and such that either xx' has decomposition loll12 ... ...lkllkl+1 or else m = 1 and I and x' have a simple composition.

  Step 3 consists of applying first Lemma 7 and then possibly Theorem 4 to the arguments 1 = z and x = x'. If the test implied by Lemma 7 fails, the comparisons of Theorem 4 are carried out simultaneously by the processors assigned to the factors of x'. The block head of B is used to identify the position of z in XXi. The remaining details are trivial at this point and are thus omitted.

Fact 7 .

 7 Let lth ... h be the Lyndon factorization of a non-empty word x. Let t be the smallest index such that It is a special factor of x. Then It .. .lkh ... lt-l is an llr of X, and

  ... x[j],then, by Fact 7, the position of such a run head is also an Isp for x[1]x[START_REF] Apostolico | Efficient Parallel Algorithms for String Editing and Related Problems[END_REF] ... x[j]. Assume now that the test preformed by Pi fails, and, setting f = j -11m(j)I, consider the prefixw = xli + I]x[i + 2) ... x[j] of ImU).Let k be the maximum length of a border of w. It is easy to see that the the factor following lm(j) in the decomposition of x[1]x[2]. .. x[j] is x[i+ III +IJx[i+111 +2] ...x[j -k]. Therefore, if k = 0, then x[i+ 111+I]x[i+III+2]... x[j]is the last factor in the decomposition of x[1 ]x[2] ... x[j] and, also the earliest special factor in such a decomposition. Otherwise, the next Lyndon word to be tested by Pi as a special factor in the decomposition of x[l]x[2] ...x[j] is xli + III + I]x[i + III + 2] ... x[j -k]. Note that Pi needs only to know k and III in order to identify this word. If also x[i+ III + l]x[i+ III +2] ... x[j -k] fails the test, then we consider its rest in the decomposition of x[l]x[2] ... x[j] and apply the same treatment to it. In conclusion, given reach:z; and a mechanism for identifying the words to be considered in succession, it takes Pi time proportional to the number of words tested in order to compute an Isp for x[l]x[2]. .. x[i]. As is easily seen, the words considered by Pi are all replicas of shorter and shorter prefixes of lm(j), and they can be identified in succession by repeated application of the function "longest border of" to such prefixes. The "longest border of" function is actually the failure /unction [1] for Im(j), and it is not difficult to show that Pi will go through at most log 11m(j)1 applications of this function during its tests. Computing the failure function for a factor I is somewhat dual to the computation of the table closel discussed earlier, and is done easily in O(log Ill) time either starting from the table reach l or by direct adaptation of the techniques in [12]. In conclusion, n processors can compute the least rotations of all prefixes of a string in O(log n) time.

  whence uc > z. But z > I t1 so that uc It_ Since h =F c, then c >>I t . Since it is a Lyndon word, then we already have that for any suffix z of It, z » It. Hence, for any f' < I, Fact 1 yields z(It)!' rest(lt)c i » (It)!rest(lt)c i . In conclusion, we is a Lyndon word, which contradicts the assumption that It is right-stable. For the second part of the proof, we show that if rest(lt) is not a prefix of It, then It is right-stable. Assume for the moment that It is not a prefix ofrest(It), i.e., neither of It or rest(It) is a prefix of the other. Then, letting v be the longest common prefix of It and rest{lt), we have Ivl < min{IItl,lrest(lt)I}. But then there are symbols a and a' such that a =1= ai, va is a prefix of It and va' is a prefix of rest(It). Now, it is known from

		Clearly,
	u	z,

1 This author's research was supported in part by the French and Italian Ministries of Education, by the British Research Council Grant SERC-E76797> by NSF Grant CCR-B9-00305, by NIH Library of Medicine Grant ROJ LM0511B, by AFOSR Grant 90-0107, and by NATO Grant eRG 900293. 2 This author's research was supported in part by PRC 'Mathematiques et Informatique' and by NATO Grant CRG 900293.