Marie-Pierre Béal
email: beal@univ-mlv.fr

Sylvain Lombardy
email: lombardy@univ-mlv.fr

Dominique Perrin
email: perrin@univ-mlv.fr

Embeddings of local automata

A local automaton is by definition such that a bounded information about the past and the future is enough to determine the present state. Due to this synchronization property, these automata play an important role for coding purposes. We prove that any irreducible local automaton is contained in a complete one. The proof uses a result from symbolic dynamics due to M. Nasu called the masking lemma. A consequence of this result in the theory of variable length codes is that any locally parsable regular code is included in a maximal one with the same synchronisation delay.

I. INTRODUCTION

The problem of embedding a finite automaton into one having specified properties is an old one in automata theory (see [START_REF] Schützenberger | A remark on incompletely specified automata[END_REF] for example). We will consider here the embedding of a local automaton into a complete one.

The embedding of an unambiguous irreducible automaton into a complete one has been solved in [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF] using a construction due to Ehrenfeucht and Rosenberg [START_REF] Ehrenfeucht | Each regular code is included in a regular maximal code[END_REF]. This result has a formulation in terms of codes. Indeed, the stabilizer of a state in an unambiguous automaton is a free submonoid. Thus the above embedding implies that any regular code is contained in a maximal one.

A local automaton is by definition such that a bounded information about the past and the future is enough to determine the present state. Formally there are integers λ, ρ such that for any pair of paths p u → q v → r and p ′ u → q ′ v → r ′ having the same label with |u| = λ and |v| = ρ one has q = q ′ . A subautomaton of a local automaton is obviously still local but conversely it is not clear how one can add transitions or states to a local automaton until it is complete, in the sense that any word on the underlying alphabet is the label of a path.

The problem of completing local automata has already been considered in [START_REF] Montalbano | Local automata and completion[END_REF], where a method is given which allows one to complete a local deterministic automaton when it is possible. We prove here that any local automaton is always contained in a complete one. Our proof relies on a result known as Nasu's masking lemma [START_REF] Nasu | Topological conjugacy for sofic systems and extensions of automorphisms of finite subsystems of topological markov shifts[END_REF].

The stabilizer of a state in a local automaton is the star of a locally parsable code (also called codes with finite synchronization delay). The previous result gives an alternative proof of a result of Bruyère [START_REF] Bruyère | On maximal codes with bounded synchronization delay[END_REF] according to which any locally parsable regular code is included in a maximal one.

In Section II, we introduce some definitions on automata equivalences. We prove our main result in Section III. We conclude with the application to locally parsable codes in Section IV.

II. EQUIVALENCES OF AUTOMATA

We denote by A = (Q, E) a finite automaton on the alphabet A with Q as set of states and E ⊂ Q×A×Q as set of edges. We consider all states as both initial and terminal. The automaton is said to be complete (with respect to the alphabet A) if for any word w ∈ A * there exists a path labelled w. It is said to be unambiguous if for any p, q ∈ Q and w in A * there is at most one path from p to q labelled w. It is said to be irreducible if for any p, q ∈ Q there is at least one word w such that there is a path from p to q labelled w.

An automaton is said to be essential if any state has at least one incoming edge and at least one outgoing edge. Clearly an irreducible automaton is essential.

An automaton A = (P, E) on the alphabet A is a subautomaton of an automaton B = (Q, F ) on the alphabet A, if

P ⊂ Q and E ⊆ F ∩ (P × A × P ).
An automaton is deterministic if for each state p and each letter a there is at most one edge labelled a going out of p.

The transition matrix of an automaton A = (Q, E) is the Q × Q matrix with elements in the set P(A) of subsets of A defined for p, q ∈ Q by M p,q = {a ∈ A | there is an edge (p, a, q) in E}.

The elements of M can be considered as elements of the semiring P(A * ) of subsets of A * , where 0 is the empty set and 1 is the set containing the empty word. Such matrices can therefore be multiplied.

Let A = (P, E) and B = (Q, F ) be two automata on the alphabet A. Let M be the transition matrix of A and let N be the transition matrix of B. We say that A and B are elementary equivalent if there exist a (P × Q)-matrix R and a (Q × P )matrix S both with elements in P(A) ∪ {1}, where 1 is the empty word, such that M = RS and N = SR. We also say that A is (R, S)-elementary equivalent to B.

This notion is classical in symbolic dynamics. It is usually formulated for subshifts of finite type (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF] p. 225). Our definition is a particular case of the notion of symbolic elementary equivalence for sofic shifts introduced in [START_REF] Nasu | Topological conjugacy for sofic systems[END_REF].

For a P × Q-matrix R with elements in P(A) ∪ {1}, we say that a triple (p, a, q) ∈ P × (A ∪ {1}) × Q is an R-edge when a ∈ R p,q . Thus when A is (R, S)-elementary equivalent to B, each edge of A is the sequence of an R-edge and a consecutive S-edge, and each edge of B is a sequence of an Sedge and a consecutive R-edge. The R-edges and S-edges can be considered as edges of a bipartite graph called the auxiliary graph of the equivalence (it is called a bipartite code in [START_REF] Nasu | Topological conjugacy for sofic systems[END_REF] and [6, p. 355]).

Example 1: Let A and B be the automata represented on Figure 1. Thus A and B are elementary equivalent. The auxiliary graph is shown in Figure 2 (with continuous lines). Let A = (Q, E) be an automaton. The input of a state q ∈ Q is the set of pairs (p, a) such that one has p a -→ q. Its output is the set of pairs (a, r) such that one has q a -→ r. An input merge equivalence is an equivalence on the set Q of states of A such that for any pair p, p ′ of equivalent states, any letter a and any state q, one has (i) p a → q if and only if p ′ a → q, (ii) q a -→ p, q a -→ p ′ implies p = p ′ . Thus, in such an equivalence, two equivalent and distinct states have the same output and disjoint inputs.

The quotient of A = (Q, E) by such an equivalence is the automaton A = (Q, E) with states the set Q of equivalence classes, and edges the induced edges on the classes, i.e. (p, a, q) ∈ E for some p, q ∈ Q implies (p, a, q) is in E.

Thus, in the quotient the output of a class of states is the common output of its elements and its input is the union, or merge, of the inputs of its elements (whence the name of an input merge equivalence). We say that A is obtained from A by an input merge. We also say that A is obtained from A by an input split .

Note that if A is an unambiguous essential automaton, there is a largest input merge equivalence. It is defined by q ≡ q ′ if q and q ′ have the same output. Indeed, since A is essential, if q ≡ q ′ , they have the same non-empty output. Since it is unambiguous, they have disjoint inputs.

Example 2: Let A, B be the automata of Example 1. The automaton A is obtained from B by an input merge. An output merge equivalence on the set of states of an automaton A is defined symmetrically. It is an equivalence on the set Q of states such that equivalent and distinct states have the same input and disjoint outputs. The quotient A is defined in the same way by merging the outputs of the elements of a class. We say that A is obtained from A by an output merge. We also say that A is obtained from A by an output split .

Observe that the quotient of an automaton A by an input or an output merge equivalence is unambiguous if and only if A is unambiguous.

The notions of input and output merge equivalence are classical in symbolic dynamics. They are usually formulated for subshifts of finite type (see [6, p. 225]). The extension of the definitions to sofic shifts is due to Nasu [START_REF] Nasu | Topological conjugacy for sofic systems[END_REF]; see also [START_REF] Krieger | On sofic systems[END_REF].

The following result is an element of William's Classification Theorem (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]).

Proposition 3: If the automaton A is obtained from the automaton B by an input (or output) merge, then A and B are elementary equivalent.

Proof: We treat the case of an input merge. Let B = (Q, E) and A = (Q, E). Let M and N be the transition matrices of A and B. Let R be the Q × Q-matrix defined for p, q ∈ Q by R p,q = {a ∈ A | there is an edge (p, a, q) in E} (note that R is well-defined because of the definition of an input merge). Let S be the Q × Q-matrix defined by S p,q = 1 if p = q 0 otherwise Then M = RS and N = SR. Thus A and B are elementary equivalent.

Proposition 4: Let A and B be two irreducible (R, S)elementary equivalent automata. Then, either R has elements in P(A) and S in {0, 1} or conversely.

Proof: Set A = (P, E) and B = (Q, F ). Suppose that there are p ∈ P , a ∈ A, and q ∈ Q such that a ∈ R pq . Let p ′ ∈ P and q ′ ∈ Q. We denote s = S q ′ p ′ . Let us show that, if s = 0 then s = 1. Since B is irreducible, there is path q u -→ q ′ labelled by u = a 1 . . . a n . We have a i = s i r i , for 1 ≤ i ≤ n, with r i ∈ R piqi , and s i ∈ S qi-1pi , and thus the path

p a -→ q 0 s1 -→ p 1 r1 -→ q 1 s2 -→ • • • sn -→ p n rn -→ q n s -→ p ′ ,
with q 0 = q and q n = q ′ . Since as 1 is the label of an edge in E, s 1 = 1. Since s 1 r 1 is the label of an edge in F , r 1 ∈ A and so on. Finally r n ∈ A and thus s = 1.

This shows that if one entry of R contains an element of A then all the entries of S are 0 or 1. Furthermore, if all the entries of S are 0 or 1, then all non-null entries of R are in P(A). The proof of the symmetrical case is similar.

We denote by L(A) the set of words labelling a finite path in A. Two automata A and B are said to be equivalent if

L(A) = L(B).
We say that two automata A and B are strongly equivalent if there is a sequence A 0 , A 1 , . . . , A n of automata such that

A 0 = A, A n = B and A i is elementary equivalent to A i+1 for 1 ≤ i ≤ n -1.
We state without proof the following Proposition. Proposition 5: Two strongly equivalent essential automata are equivalent.

We will now describe a construction due to Nasu (see [6, p. 354], Lemma 10.2.3). It associates to automata A 1 , A 2 , B 1 such that A 1 is elementary equivalent to A 2 and A 1 is a subautomaton of B 1 , an automaton B 2 elementary equivalent to B 1 and such that A 2 is a subautomaton of B 2 . The automaton B 2 is called the Nasu embedding of A 2 with respect to A 1 , B 1 . The intuitive idea behind the construction is to cut the edges of B 1 in to halves and to create a new state in the middle which is a state of B 2 .

Set

A 1 = (P 1 , E 1 ), A 2 = (P 2 , E 2 ) and B 1 = (Q 1 , F 1 )
. Let R, S be matrices such that RS and SR are respectively the transition matrices of

A 1 and A 2 . Let Q 2 = P 2 ∪ (F 1 \ E 1 ). We define a Q 1 × Q 2 -matrix R and a Q 2 × Q 1 -matrix S as follows.
Suppose first that R has 0, 1 entries and S entries in P(A). Then, for q 1 ∈ Q 1 and q 2 ∈ Q 2 , we define

R q1,q2 =    R q1,q2 if q 1 ∈ P 1 , q 2 ∈ P 2 1 if q 2 ∈ F 1 \ E 1 and o(q 2 ) = q 1 0 otherwise and S q2,q1 = S q2,q1 ∪ {l(q 2 ) | q 2 ∈ F 1 \ E 1 , e(q 2 ) = q 1 },
where o(q 2 ) denotes the origin of q 2 , l(q 2 ) its label, and e(q 2 ) its end. An illustration of this construction is given in Example 7.

In the case where R has entries in P(A) and S has 0, 1 entries, we define

R q1,q2 = R q1,q2 ∪{a ∈ A | q 2 ∈ F 1 \E 1 , o(q 2 ) = q 1 , l(q 2 ) = a} and S q2,q1 =    S q2,q1 if q 1 ∈ P 1 , q 2 ∈ P 2 1 if q 2 ∈ F 1 \ E 1 and e(q 2 ) = q 1 0 otherwise .
It is clear that in both cases, R S is the transition matrix of B 1 . The automaton B 2 = (Q 2 , F 2 ) is defined by its transition matrix which is S R. To sum up, we have the following statement.

Proposition 6: Let A 1 , A 2 , B 1 be automata such that A 1 is a subautomaton of B 1 and A 1 is elementary equivalent to A 2 . Let B 2 be the Nasu embedding of A 2 with respect to A 1 , B 1 . Then A 2 is a subautomaton of B 2 and B 1 is elementary equivalent to B 2 . Moreover, if A 2 and B 1 are irreducible (resp. essential), then B 2 is irreducible (resp. essential). denotes the transition matrix of the automaton A i (resp. B i ) of Figure 3, we have

A 1 = a b a b = RS = 1 1 a b , A 2 = a + b = SR. B 1 =   a b 0 a b c 0 d 0   = R S =   1 0 0 1 1 0 0 0 1     a b 0 0 0 c 0 d 0   , B 2 =   a + b b 0 0 0 c d d 0   = S R =   a b 0 0 0 c 0 d 0     1 0 0 1 1 0 0 0 1   .

III. LOCAL AUTOMATA

An automaton is said to be (λ, ρ)-local if for all pairs of paths p u → q v → r and p ′ u → q ′ v → r ′ with |u| = λ and |v| = ρ, one has q = q ′ . The automaton is said to be local if it is (λ, ρ)-local for some λ, ρ ≥ 0. An automaton which has a single state is (0, 0)-local.

Thus in a local automaton, one can recover a biinfinite path from its label using a sliding window of fixed size.

A word w is said to be a constant for an automaton A if for two paths p w → q and p ′ w → q ′ with label w, one has also p w → q ′ and p ′ w → q. The empty word is a constant only when the automaton has a single state.

Note that if A is a (λ, ρ)-local automaton, then an input split of A is a (λ + 1, ρ)-local automaton, and an output split of A is a (λ, ρ + 1)-local automaton.

An automaton is said to have order n if any word of length n is a constant. Note that a (λ, ρ)-local automaton has order λ + ρ. The minimal order can however be strictly less than λ+ρ. An unambiguous automaton with order n is (n, n)-local.

Let λ, ρ ≥ 0. The free (λ, ρ)-local automaton is the automaton with set of states consisting of pairs (u, v) of words, with u of length λ and v of length ρ, and edges the triples ((u, v), a, (u ′ , v ′ )) such that there are letters b, c with uvc = bu ′ v ′ and a is the first letter of vc. It is clear that this automaton is (λ, ρ)-local and complete.

The free (n, 0)-local automaton is usually known as the de Bruijn automaton of order n.

Lemma 8: The free (λ, ρ)-local automaton has order max(λ, ρ).

Proof: Set n = max(λ, ρ). Let F (λ,ρ) be the free (λ, ρ)local automaton. Let (u, v) w -→ (x, y) and (u ′ , v ′ ) w -→ (x ′ , y ′ ) be two paths labelled w of length n in F (λ,ρ) , with u, u ′ , x, x ′ of length λ and v, v ′ , y, y ′ of length ρ. Since λ, ρ ≤ n, v, v ′ are prefixes of w and x, x ′ are suffixes of w. Hence v = v ′ and x = x ′ and there are paths (u, v) w -→ (x, y ′ ) and (u ′ , v) w -→ (x, y) in F (λ,ρ) . This shows that F (λ,ρ) has order n.

Example 9: The free (1, 1)-local automaton on the alphabet {a, b} is represented on Figure 4. The label of an edge going out of a state is its second letter. The following result shows that any (λ, ρ)-local automaton is strongly equivalent to a subautomaton of the free (λ, ρ)-local automaton.

Proposition 10: If A is (λ, ρ)-local automaton, there is a sequence A 0 , A 1 , . . . , A λ+ρ of (λ, ρ)-local automata such that (i) A 0 = A.

(ii) For i = 0, . . . , λ -1, A i is obtained from A i+1 by an input merge. (iii) For i = λ, . . . , λ + ρ -1, A i is obtained from A i+1 by an output merge. (iv) A λ+ρ is a subautomaton of the free (λ, ρ)-local automaton. Proof: Let A = (P, E). We define for 1 ≤ i ≤ λ, A i = (P i , E i ) where P i is the set of pairs (u, q) with u ∈ A i and q ∈ P such that there is a path labelled u leading to q in A. There is an edge labelled a from (u, p) to (v, q) in A i if u = bu ′ , v = u ′ a for b ∈ A and (p, a, q) ∈ E. For j = 1, . . . , ρ, let A λ+j = (P λ+j , E λ+j ) where P λ+j is the set of triples (u, p, v) ∈ A λ × P × A j such that there is a path labelled u leading to p and a path labelled v leaving p in A.

There is an edge labelled a from (u, p, v) to (w, q, t) if and

only if u = bu ′ , w = u ′ a, v = av ′ , t = v ′ c and (p, a, q) ∈ E.
For 0 ≤ i ≤ λ -1, the equivalence θ i+1 on P i+1 defined by (u, p) ≡ (u ′ , p ′ ) if p = p ′ and u, u ′ differ at most by the first letter is an input merge. Similarly, for λ

≤ i ≤ λ + ρ -1, the equivalence θ i+1 on P i+1 defined by (u, p, v) ≡ (u ′ , p ′ , v ′ ) if u = u ′ , p = p ′
and v, v ′ differ at most by their last letter, is an output merge. This shows that conditions (ii) and (iii) are satisfied.

Finally, since A is (λ, ρ)-local, in a state (u, p, v) of A λ+ρ , the state p is determined by (u, v). Thus condition (iv) is also satisfied.

Observe that if A is moreover supposed to be irreducible, then all the automata A i constructed as above are also irreducible.

We will prove the following result.

Theorem 11: Any irreducible (λ, ρ)-local automaton is a subautomaton of a complete irreducible local automaton of order max(λ, ρ). Note that this statement implies that any irreducible local automaton of order n is a subautomaton of a complete irreducible local automaton of order n.

The proof uses Nasu embeddings. Proposition 12: Let A 1 and A 2 be automata such that A 2 is obtained from A 1 by input (or output) merge. If A 1 is a subautomaton of a local automaton B 1 of order n, then the Nasu embedding of A 2 with respect to A 1 and B 1 , is a local automaton of order n.

Proof: We treat the case of an input merge. The case of an output merge is symmetrical. Let B 1 = (Q 1 , F 1 ) be a local automaton containing A 1 = (P 1 , E 1 ) as a subautomaton. Assume that

A 2 = (P 2 , E 2 ) is obtained from A 1 by input merge. Let F = F 1 \ E 1 , Q 2 = P 2 ∪ F and let B 2 = (Q 2 , F 2 ) be the Nasu embedding of A 2 with respect to A 1 , B 1 .
Let R, S be the matrices defined as in the proof of Proposition 3. The transition matrix of A 1 is equal to RS while the transition matrix of A 2 is equal to SR. We have a ∈ S p,q if (p, a, q) ∈ E 1 and R p, p = 1. The additional S-edges are the triples (f, a, q) such that f = (p, a, q) is in F . The additional R-edges are the triples (p, 1, f ) such that f begins with p. An example of this construction is described in Figure 3.

Let π be the map defined on the set P of paths of B 1 of length at least 2 onto the set of nonempty paths of B 2 as follows. If (e 0 , e 1 , . . . , e n ) ∈ P with e i = (q i , a i , q i+1 ), we define π(e 0 , e 1 , . . . , e n ) = (g 0 , g 1 , . . . , g n-1 ) with g i = (p i , a i , p i+1 ) defined by p i = qi if e i ∈ E 1 and p i = e i if e i ∈ F .

We claim that π is a surjective map from the set P onto the set of nonempty paths of B 2 . We have to verify that each g i is an edge of B 2 . We distinguish four cases.

(i) If p i , p i+1 ∈ P 2 . Then g i is an edge of A 2 and thus of B 2 . It is the concatenation of an S-edge and an R-edge. (ii) If p i ∈ P 2 and p i+1 ∈ F . Then p i = qi and p i+1 = e i+1 . Thus g i is the concatenation of an S-edge and an ( R -R)-edge. (iii) If p i , p i+1 are in F , then p i = e i and p i+1 = e i+1 . Thus g i = (p i , a i , p i+1 ) is the concatenation of an ( S -S)edge and an ( R -R)-edge. (iv) If p i ∈ F and p i+1 ∈ P 2 then p i = e i . Thus g i is the concatenation of an ( S -S)-edge and an R-edge. Thus π is well defined. Moreover, one can verify that for any nonempty path c in B 2 there exists c ′ ∈ P such that π(c ′ ) = c. Thus π is surjective.

Let n be the order of B 1 . Let c = p w → q and c ′ = p ′ w → q ′ be two paths in B 2 with |w| = n. Then there exist paths

d = r w → s a → t and d ′ = r ′ w → s ′ a ′ → t ′ in B 1 , with a, a ′ ∈ A, such that π(d) = c and π(d ′ ) = c ′ . Since B 1 has order n, w is a constant for B 1 . Thus we have also paths e = r w → s ′ a ′ → t ′ and e ′ = r ′ w → s a → t in B 1 .
It is easy to verify that π(e) is a path from p to q ′ and π(e ′ ) a path from p ′ to q. Thus w is a constant for B 2 .

We now prove Theorem 11.

Proof: Let A be an irreducible (λ, ρ)-local automaton. By Proposition 10 there is a sequence A 0 , A 1 , . . . , A λ+ρ of automata such that A = A 0 , A λ+ρ is a subautomaton of the free (λ, ρ)-local automaton and each A i is a merge of A i+1 . By Lemma 8, the free (λ, ρ)-local automaton has order n = max(λ, ρ). Since A λ+ρ is included in the free (λ, ρ)-local automaton, we may build using repeatedly Proposition 12 a sequence B λ+ρ , . . . , B 1 , B 0 of complete local irreducible automata with order n such that A i is contained in B i for i = λ + ρ, . . . , 0. Thus B = B 0 is a complete local automaton with order n containing A. Since A is irreducible, all A i and B i are irreducible.

Example 13: Let A = A 0 be the deterministic automaton represented on the left of Figure 5. It is (3, 0)-local and has order 3. The automaton A cannot be completed in a local deterministic automaton (see [START_REF] Montalbano | Local automata and completion[END_REF]). We have represented on the right of Figure 5 a split A 1 of A, obtained by an input split of state 2 in two states 5 and 7. This automaton can easily be completed as indicated on the right of Figure 5. The auxiliary graph is shown on the left of Figure 6. The final result is shown on the right of Figure 6. It is a complete local automaton containing A. IV. APPLICATION TO LOCALLY PARSABLE CODES In this section, we briefly show how our result applies to the theory of variable length codes.

A variable length code (or code) is a set X of finite words which is uniquely decipherable: x 1 x 2 . . . x n = y 1 y 2 . . . y m , with x i , y j ∈ X, implies n = m and x i = y i for all i.

Let X be a code. A word w is a constant for X * if uwv, u ′ wv ′ ∈ X * implies uwv ′ , u ′ wv ∈ X * . A code X has literal synchronization delay s if any word of A s is a constant for X * . A code is locally parsable (or has finite synchronization delay) if there is an integer s such that it has literal synchronization delay s.

The stabilizer of a state in a local automaton with order s is X * , where X is a locally parsable code with synchronization delay s. Conversely, if X is a locally parsable regular code with synchronization delay s, one can build an irreducible (s, s)-local automaton such that X * is the stabilizer of some state (see [START_REF] Berstel | Codes and Automata[END_REF].)

Since our result allows to complete this automaton in a complete one of order s, it gives a maximal regular locally parsable code Y containing X which has the same synchronization delay as X.

For instance, the code X = {aba, baba}, which has literal synchronization delay 3 can be completed into the regular code Y = ab ∪ (a + ∪ (a + ∪ b)b + a which has literal synchronization delay 3. An automaton recognizing Y * is given on the right of Figure 6, with state 1 as initial and final state.

This gives an alternative proof of a result of Bruyère according to which any locally parsable regular code is included in a maximal one [START_REF] Bruyère | On maximal codes with bounded synchronization delay[END_REF] where the conservation of the delay was not guaranteed.

Fig. 1 .

 1 Fig. 1. Two elementary equivalent automata A (on the left) and B (on the right).

1 Fig. 2 .

 12 Fig. 2. The auxiliary graph (with continuous edges).

Example 7 :Fig. 3 .

 73 Fig.3. The Nasu embedding B 2 of A 2 with respect to A 1 , B 1 . The automata A 1 = (P 1 , E 1 ) with P 1 = {2, 3} and A 2 = (P 2 , E 2 ) with P 2 = {1} are represented with continuous edges. We haveB 1 = (Q 1 , F 1 ) with Q 1 = {2, 3, 4} and B 2 = (Q 2 , F 2 ) with Q 2 = {1,c, d}. The automaton B 2 has two additional states c, d corresponding to the additional edges (3, c, 4) and (4, d, 3) of B 1 . The transitions defined by R and S are represented with dashed edges. Additional states and edges are represented with dots.

Fig. 4 .

 4 Fig. 4. The free (1, 1)-local automaton. It has order 1.

Fig. 5 .

 5 Fig. 5. A local automaton A (on the left) and a split A 1 of A with its completion B 1 with the dotted edges (on the right)

Fig. 6 .

 6 Fig.6. The auxiliary graph (with continuous edges) on the left. The automata A and A 1 on the left are represented with dashed edges and the additional edges with dotted lines. The result on the right is the embedding of A with respect to A 1 and B 1 . This automaton has order 3 although it is (3, 1)-local.

Acknowledgements: We would like to thank Brian Marcus who pointed out to us the possibility of using Nasu's masking lemma in this problem. We also thank the referees who helped us to improve the presentation.


Marie-Pierre Béal
email: beal@univ-mlv.fr

Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Minimizing incomplete automata

Keywords: algorithms, automata, minimization, partitioning

We develop a O(m log n)-time and O(k + n + m)-space algorithm for minimizing incomplete deterministic automata, where n is the number of states, m the number of edges, and k the size of the alphabet. Minimization reduces to the partial Functional coarsest partition problem. Our algorithm is a slight variant of Hopcroft's algorithm for minimizing deterministic complete automata.

Introduction

It is well known that rational languages may be represented equivalently as rational expressions or as deterministic finite automata. Among them, there exists up to a renaming of states a unique minimal automaton accepting a given rational language (see for example [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF]). This automaton is indeed the morphic image of any automaton accepting the language.

The description of a language with its minimal automaton is important when space considerations matter in implementations of applications, such as in Pattern Matching or in Coding Systems, for example.

There are several ways to get the minimal automaton of a language. If operations on languages are feasible, the method based on quotient languages produces it directly (see [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF][START_REF] Pin | Varieties of formal languages[END_REF]). However, partitioning is the basic strategy to minimize automata. It is also stated as the Functional coarsest partition problem, in which the question is to compute a coarsest partition of a finite set that is compatible both with marked elements and a finite set of functions defined on the set. Existing algorithms assume that functions are everywhere defined, or equivalently that the automaton is complete. If it is not, completion is a straightforward operation but requires additional space. The simplest efficient algorithms to minimize an automaton is by Moore and runs in time O(kn 2 ) for a (deterministic) automaton with n states on an alphabet of size k. The fastest known solution by Hopcroft [START_REF] Hopcroft | An nlogn algorithm for minimizing states in a finite automaton[END_REF][START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF] runs in time O(kn log n) (see also [START_REF] Gries | Describing an algorithm by hopcroft[END_REF][START_REF] Blum | An O(n log n) implementation of the standard method for minimizing n-state finite automata[END_REF][START_REF] Knuutila | Re-describing an algorithm by hopcroft[END_REF]). The design implement a so-called "smaller half" strategy. The complexity of the problem is still an open question but there is a family of automata on which Hopcroft's algorithm runs effectively in Θ(n log n) [START_REF] Berstel | On the complexity of Hopcroft's state minimization algorithm[END_REF].

The minimal automaton of a language can also be built directly for some rare specific languages like the set of strings ending with a given string [START_REF] Crochemore | Algorithms on Strings[END_REF] or the set of suffixes of a string [START_REF] Crochemore | Transducers and repetitions[END_REF], for example. In this two cases the algorithms can even be implemented to run in linear time. But most often the minimization step has to be done after the construction of a deterministic automaton accepting the considered language, as for automata obtained from rational expressions (see [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF]). Although the notion of a minimal automaton does not exist for non-deterministic automata, it is still possible to find equivalent automata with the minimum number of states (see [START_REF] Ilie | Reducing NFAs by invariant equivalences[END_REF][START_REF] Ilie | On NFA reductions[END_REF]), but the problem is known to be computationally hard [START_REF] Jiang | Minimal NFA problems are hard[END_REF].

It is rather simple to see that minimization can be achieved in linear time when the alphabet has only one letter (k = 1) [START_REF] Paige | A linear time solution to the single function coarsest partition problem[END_REF]. The solution makes use of the particular structure of the automaton and of some string algorithms. But the solution does not seem to extend to larger alphabets.

Another known situation for which a linear-time algorithm exists is the case of finite languages [START_REF] Revuz | Minimisation of acyclic deterministic automata in linear time[END_REF] (O(kn) running time reducible to O(n) with the technique of the present paper) and the specific aforementioned languages.

Hopcroft's strategy with a slight modification also works for partitioning a graph or equivalently a non-deterministic automaton on a one-letter alphabet [START_REF] Cardon | Partitioning a graph in O(A log 2 V ). Theoret[END_REF][START_REF] Paige | Three partition refinement algorithms[END_REF] leading to O(m log n) running time algorithms. To do so, the "smaller half" technique is replaced by the "all but the largest" strategy as the one we use here.

To achieve an O(m log n) running time for minimizing local automata, we use in [START_REF] Béal | Minimizing local automata[END_REF] a procedure for merging states having the same immediate future instead of Hopcroft's method that relies on state discrimination.

When a complete deterministic automaton is given, its size is O(kn) and Hopcroft's algorithm adds a mere log n factor to minimize it. But when the automaton is incomplete, the actual size of the automaton assumed to contain no useless state is O(m), where m its number of edges, which ranges from n to kn. Room for improvement is larger here than just dropping the log factor of Hopcroft's algorithm, which requires a complete automaton.

Another solution reaching the same running time as ours has been published recently by Valmari and Lehtinen [START_REF] Valmari | Efficient minimization of DFAs with partial transition functions[END_REF]. Their solution uses the "smaller half" strategy as Hopcroft's algorithm does. But in addition to Hopcroft's method managing state partitions, they maintain a partition of transitions to have a direct access to edges labeled by a given letter and coming in a block splitter used later in the partitioning process. Both partitions are refined at the same time.

We develop in the rest an O(m log n)-time and O(k +n+m)-space algorithm for minimizing incomplete deterministic automata. Our method uses three ingredients. The first one is the "all but the largest" strategy, a generalization of the "smaller half" strategy, which is used in [START_REF] Cardon | Partitioning a graph in O(A log 2 V ). Theoret[END_REF]. In this strategy, a block can be split in more than two pieces and only the largest piece does not become a splitter. The second ingredient is the notion of signature of a state, which represents its outgoing labeled edges, notion that is used successfully to get a linear-time algorithm for minimizing acyclic automata [START_REF] Revuz | Minimisation of acyclic deterministic automata in linear time[END_REF] and local automata [START_REF] Béal | Minimizing local automata[END_REF]. The third ingredient is "weak sorting" [START_REF] Paige | Efficient translation of external input in a dynamically typed language[END_REF], which is used as well in [START_REF] Valmari | Efficient minimization of DFAs with partial transition functions[END_REF], although they do not refer to it. We believe that our solution provides a simpler description of the whole algorithm.

Minimizing incomplete deterministic automata 2.1 Functional coarsest partition

Let A = (U, F, T ) be a deterministic (incomplete) automaton over a finite alphabet A. The notation means that U is the set of states, F is the set of edges, T is the set of final states. No initial state is specified since it does not play any role in the minimization process. A successful path is a path ending in a final state. We assume that the automaton is trim, i.e., each state is co-accessible: there is at least one successful path starting from this state. This assumption is important to guarantee the correctness of the algorithm. But we do not assume that the graph underlying the automaton is connected.

We denote by E the sequence of partial relations (E a ) a∈A defined by (p, q) ∈ E a if and only if (p, a, q) is an edge of A. Indeed, all these relations are (partial) functions because the automaton is deterministic.

For any subset S ⊆ U , any letter a ∈ A, let

E a (S) = {q | ∃p ∈ S (p, a, q) ∈ F }, E -1 a (S) = {p | ∃q ∈ S (p, a, q) ∈ F }. Let also E(S) = ∪ a∈A E a (S) and E -1 (S) = ∪ a∈A E -1 a (S). If p is a state, we shall write E a (p) and E -1 a (p) instead of E a ({p}) and E -1 a ({p}) respectively. If E a (p) is not empty and B ⊆ U , we shall write E a (p) ∈ B instead of E a (p) ⊆ B since E a (p) is a singleton. If B ⊆ U and S ⊆ U , B is said to be stable with respect to S if, for any a ∈ A, either B ⊆ E -1 a (S) or B ∩ E -1 a (S) = ∅.
If P is a partition of U , P is stable with respect to S if all the blocks (classes) of P are stable with respect to S. A partition P is stable if it is stable with respect to each of its own blocks.

Let Q and R be two stable partitions finer than a partition P . The partition Q ∪ R obtained by merging the blocks of Q and R having a non-empty intersection is stable, coarser than Q and R, and finer than P . There is thus a coarsest stable refinement of P .

The partial functional coarsest partition problem is that of finding, for a sequence of partial functions (E a ) a∈A and an initial partition P over a set U , the coarsest stable refinement of P , i.e., the partition which admits every stable partition as a refinement. The coarsest partition has the fewest blocks among all stable partitions. This partition defines the minimal automaton when the initial partition distinguishes final and non-final states.

In discussing time bounds for this problem, we let k denote the size of the alphabet A, n denote the size of set of states U , and m denote the size of E which is the sum of sizes of E a , i.e., the number of edges of the automaton A.

The (complete) functional coarsest partition problem (when all E a are complete functions) was solved by Hopcroft in time O(kn log n) [START_REF] Hopcroft | An nlogn algorithm for minimizing states in a finite automaton[END_REF] and space O(k × n) with a process known as the "smaller half strategy"(see for instance [START_REF] Beauquier | Éléments d'algorithmique[END_REF], [START_REF] Gries | Describing an algorithm by hopcroft[END_REF], or [START_REF] Knuutila | Re-describing an algorithm by hopcroft[END_REF] for an implementation with this time complexity). The relational coarsest partition problem (when E is a relation) was solved by Cardon and Crochemore [START_REF] Cardon | Partitioning a graph in O(A log 2 V ). Theoret[END_REF] in time O(m log n) and space O(n + m) (see also [START_REF] Paige | Three partition refinement algorithms[END_REF]). Another kind of partitioning, namely s-partitioning with a one-letter alphabet, has been designed in linear time by Paige, Tarjan, and Bonic [START_REF] Paige | A linear time solution to the single function coarsest partition problem[END_REF].

We design a O(m log n)-time and O(k+n+m)-space algorithm for the partial functional coarsest partition problem which is a slight variant of Hopcroft's algorithm which works in the complete case. As a consequence, it is simpler than Paige and Tarjan's algorithm for the relational coarsest partition problem. Our algorithm provides a O(m log n)-time and O(k + n + m)-space algorithm for minimizing an incomplete deterministic automaton.

Description of the algorithm

For any partition Q and subset S ⊆ U , we denote by split(S, Q) the refinement of Q obtained by replacing each block B ∈ Q by the blocks (B i ) i∈P(A) defined by

B i = {p ∈ B | ∀a ∈ i, E a (p) ∈ S and ∀a / ∈ i, E a (p) is empty or E a (p) / ∈ S}.
In this operation the set S is called the splitter.

Lemma 1. Let S be the union of some blocks of a partition Q that is stable relative to S and let B ⊆ S be a block of Q. Then split(B, Q) is stable with respect to S -B.

Proof. Indeed, let B i be a block of split(B, Q), where i ∈ P(A). The block B i is stable with respect to B, i.e., for any letter a,

B i ⊆ E -1 a (B) or B i ∩E -1 a (B) = ∅. If B i ⊆ E -1 a (B), we have B i ∩E -1 a (S -B) = ∅ since E a is a partial function. Let us now assume that B i ∩ E -1 a (B) = ∅. Since B i is stable with respect to S, we have either B i ∩ E -1
a (S) = ∅, and hence

B i ∩ E -1 a (S -B) = ∅, or B i ⊆ E -1 a (S). In the latter case, B i ⊆ E -1 a (S) -E -1 a (B) and hence B i ⊆ E -1 a (S -B). Which shows that split(B, Q) is stable with respect to S -B.
The previous statement means that split(B, Q) = split(S -B, Q). This is the idea of Hopcroft's algorithm for the functional coarsest partition problem, which is still valid in the case of partial functions. The two following algorithms refine an initial partition Q.

Hopcroft(A = (U, F, T )) 1 L ← (smallest of T and U \ T ) 2 while L = () 3 do S ← extract first of L 4 for each a ∈ A 5 do Q ← 2split(S, Q, a) 6
for each set P split into non empty sets P 1 and P 2 7

do L ← L•(smallest of P 1 and P 2 ) 8 return Q

Minimization(A = (U, F, T )) 1 L ← (T, U \ T ) 2 while L = () 3 do S ← extract first of L 4 Q ← split(S, Q) 5
for each set P split into non empty blocks P 1 , P 2 , . . , P r 6 do L ← L•(all but the largest of P i ) 7 return Q

The second algorithm maintains a queue L of possible splitters, initially containing every block of the initial partition P . The algorithm consists in initializing Q = P and applying the following step until L is empty, at which time Q is the coarsest stable refinement:

Refine: Remove from L its first set S. Replace Q by split(S, Q). Whenever a block B ∈ Q splits into two or more nonempty blocks, add all but the largest to the back of L.

The correctness of this algorithm follows from the fact that if Q is stable with respect to a set S and P is split into smaller blocks P 1 , P 2 , . . P r , then refining with respect to all but one of the sets P i guarantees the stability with respect to the last one.

The property of being finer than the initial partition P is invariant during the computation. Let Q be the partition obtained at the final step and R be any other stable partition finer than P . Then Q ∪ R is a stable partition finer than P . Let Q i be the finest partition computed during the process which is coarser than

Q ∪ R. If Q ∪ R = Q, there is a block B ∈ Q ∪ R
which is not stable under some block of Q i , i.e., under some union of blocks of Q ∪ R. Thie implies that B is not stable under some block of Q ∪ R, which contradicts the stability of Q ∪ R. This proves that the algorithm computes the coarsest coarsest stable refinement of P .

To minimize an incomplete deterministic automaton A = (U, F, T ), where U is the set of states, F the set of edges, and T the set of terminal states, we have to compute the Nerode partition of the set of states.

Let p be a state of A. We denote by F (p) the set of words u that are labels of a successful path starting from p. It is called the future of the state p. Two states p and q are said to be Nerode equivalent if and only if F (p) = F (q). The Nerode partition is the partition induced by the Nerode equivalence. States of the minimal automaton are blocks of Nerode partition, edges and terminal states are defined accordingly.

The minimization algorithm is obtained by initializing the partition Q of states to P = {T, U -T }. The list L initially contains the two blocks of P .

Lemma 2. The partition of states computed by the algorithm Minimization starting with Q = {T, U -T } is the Nerode equivalence, that is, the coarsest stable refinement of {T, U -T }.

Proof. The correctness of this algorithm follows from the fact that the Nerode partition N is a stable partition which is finer than the initial partition. Indeed, the Nerode partition is by definition finer than the initial partition P = {T, U -T }. Let us show that it is stable. Let us assume that there are blocks B, S of N and p, q ∈ S such that E a (p) ∈ B and E a (q) / ∈ B. Hence E a (p) and E a (q) are not Nerode equivalent and p and q neither. Let us now assume that p, q ∈ S are such that E a (p) ∈ B and E a (q) is the empty set. Since E a (p) is co-accessible, p, q are not Nerode equivalent. Hence N is stable.

Conversely, we show that the Nerode partition is not finer than the coarsest stable refinement Q of P = {T, U -T }. Let us assume that it is false. Let p, q be two states in a same block B 0 of Q such that F (p) = F (q). Then there is for instance a word u and a successfull path (p i , a i , p i+1 ) 0≤i≤r-1 labelled by u starting from p such that there is no successfull path labelled by u starting from q. Let v be the longest prefix of u such that there is a path (q i , a i , q i+1 ) 0≤i≤s-1 labelled by v starting from q. Since Q is stable, p i , q i for 0 ≤ i ≤ s belong to a same block B i of Q. If v = u, then p r ∈ T and q r / ∈ T which contradicts the fact that Q is finer than {T, U -T }. If v = u, s < r and B s is not stable under the block of Q containing E as+1 (p s ) which is contradiction.

Description of the implementation

The implementation of the algorithm is analogue to Hopcroft's implementation of [START_REF] Beauquier | Éléments d'algorithmique[END_REF] (see also [START_REF] Paige | Three partition refinement algorithms[END_REF] or [START_REF] Lothaire | Applied combinatorics on words[END_REF]Chapter 1]) despite the fact that the splittings of blocks become more complicated, because a block can be split into more than two pieces. Moreover, in order to get the claimed complexity, the splittings according to a block cannot be done sequentially for each letter of the alphabet. Most of this section is devoted to the description of the splitting procedure.

An efficient implementation requires several data structures. We represent each state p ∈ U by a record (or structure) that we shall not distinguish from the state itself. We represent each block of a partition Q by a record that we shall not distinguish from the block itself. The blocks are numbered. We represent the partition Q by a doubly linked list of blocks. The edges (i.e., the elements of all E a ) are records. The various records are linked together in the following way. Each state p points to an unordered list of the edges (p, a, q) (i.e., the pairs (p, q) ∈ E a for some a), the list the edges going out from p. Each state q points to an unordered list of the edges (p, a, q), the list of the edges coming in q. This allows scanning the set E -1 (q) in time proportional to the number of its incoming edges. It also allows the scanning of all E -1 (q), for all states q of a block B, in time proportional to the total size of the list of the edges coming in the block B. This scanning and the operations performed during it are described more precisely below.

Each block of Q has an associated integer giving its size and points to a doubly linked list of the elements in it. The double linking allows deletion in O(1) time. Each state of U points to the unique block of Q containing it. The space needed for all the data structures is O(n + m).

We now describe the splitting procedure under a splitter B ∈ Q. To each state p of ∪ q∈B E -1 (q) is associated a set set(p) whose elements are the letters a such that there is an edge labelled by a from p to a state in B. Each set has no duplicate elements. We denote by set(p) + the set set(p) augmented by the block number of p. We then perform a set dicrimination of the states, i.e., the states are discriminated according to their associated set set(p) + . We use a technique called weak sorting in [START_REF] Paige | Efficient translation of external input in a dynamically typed language[END_REF] which sorts all the sets according to an arbitrary total order computed by the algorithm. A weak sort can be seen as a weak form of a radix sort. It takes linear time in the sum of the number of elements in each set.

Produre split(Q, B):

Weak sort the states p in ∪ q∈B E -1 (q) according to their associated set set + (p).

We now detail the steps of the weak sort. In a first step, we compute the set of letters a such that E -1 a (B) is not empty, and for each such letter, we compute the set of states p such that set(p) contains a.

Step 1: bucket initialization. During the scanning of the lists E -1 (q) for all q ∈ B, we compute

• an (unordered) linked list ℓ representing the set of letters a labels of some edge coming in B, • for each letter a ∈ ℓ, the list ℓ(a) of states p in U such that p ∈ E -1 a (B).

This computation is done in time O(|B| + p∈B |E -1 (p)|) and space O(k) with the use of a table t of size k for which t[a] points to the list ℓ(a). Each state p for which (p, a, q) is scanned is added to the bucket list ℓ(a).

In a second step, we compute the signatures the states contained in the above buckets. If p is a state contained in at least one list ℓ(a), its signature σ(p) is the list of elements of set(p), i.e., whose elements are the letters a for which there is an edge labelled by a from p to a state in B, in the order given by the list ℓ. Note that different signatures may have different lengths.

Step 2: computation of the signatures. We scan the list ℓ and, for each a ∈ ℓ, we scan the list ℓ(a), updating the signature of each state p. During this scanning we build an (unordered) linked list s of the states p belonging to at least one list ℓ(a). This computation is done in time O( p∈B |E -1 (p)|) and space O(n) with the use of a table σ of size n such that σ[p] points to the signature of p. Lists ℓ(a) are emptied after their scanning.

Note at this step that two states p, q belonging to a same block S before the splitting under B will belong to a same block after the splitting if and only if they have the same signature.

In a third step, we discriminate the states p contained in the above buckets with respect to their set set + (p). Two states having the same signature will be contiguous in the final list.

Recall that t is a table indexed by the letters of the alphabet. Let t b be a table indexed by the possible block numbers (hence of size at most n). Let ℓ 1 be a linked list representing a set of block numbers and ℓ 2 be a linked list representing a set of letters. Both lists are without repetitions. Thus an element is added to the list only if it is not already contained in the list. The two lists are initially empty. We first discriminate with respect to the block number, and then with respect to the signatures. In order to simplify the presentation, we first assume that all signatures of the states in s have the same length r.

Step 3: Discrimination of the states. For each state p in the list s do • let i be the the number of the block containing p, • add (in constant time) the number i to the list ℓ 1 , • add the state p at the end of the list t

b [i].
The list s is then made empty and, for each block number i in the list ℓ 1 , we concatenate the list t b [i] at the end of s.

For j from 1 to r do • For each state p in the list s do add the state p at the end of the list t[a], where a is the letter number j of the signature of p. -add this letter a to ℓ 2 .

• Empty the list s and, for each letter a in the list ℓ 2 , concatenate the list t[a] at the end of s.

In the case where signatures are not of constant length, we first discriminate the states according to the length of their signature and apply the above procedure to each bucket. The discrimination is performed in time O( p∈B |E -1 (p)|) and space O(n + k). Note that the tables t, t b do not need to be initialized by the use of sparse list implementation (see for instance [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF] Exercise 2.12 p. 71).

At the end of the third step, the list s of states satisfies the property that two states belonging to a same block of Q and having the same signature are contiguous in s. The split blocks are obtained in the final Step 4.

Step 4: Splitting of the blocks. We scan the list s obtained at the end of the third step and put two states belonging to a same block B of Q and having the same signature in a same split block B i . States in the same block B i are extracted from B. Sizes of B, B i are updated during the extraction.

Step 4 requires a time O( p∈B |E -1 (p)|) and no additional space.

Example 1. We illustrate the weak sort. Let A = (U, F, T ) be the automaton of Figure 1. The initial list of states in step 3 is s = (2, 1, 3). The final list obtained after the weak sort is s = (2, 1, 3) and U is split into U 1 = {2, 1} and U 2 = {3}.

The overall time complexity is obtained with classical arguments used for Hopcroft's algorithm. A given state p ∈ U is in at most log 2 n different blocks B considered as splitters, since each successive such set is at most half the size of the previous one. Indeed, when a block S is split into sets S i , all but the largest are becoming future splitters. Therefore we have described an implementation in which a refinement step with respect to a block B takes O(|B|+ p∈B |E -1 (p)|) time. From this a O(m log n) overall time bound on the algorithm follows by summing over all blocks B used for refinement and over all elements in such blocks. The space complexity is O(k + n + m).

The conclusion lies in the next statement.

Figure 1 :

 1 Figure 1: A deterministic incomplete automaton A = (U, F, T ) over the alphabet A = {a, b, c}. All states are final. Let P = {U } be the initial partition of U . We detail the splitting under the block U = {1, 2, 3}. We successively get ℓ = (c, a, b), ℓ(a) = 3, ℓ(b) = 1, 2, ℓ(c) = 2, 1.

Theorem 3 .

 3 An incomplete automaton with n states, m edges, and k letters can be minimized in time O(m log n) and memory space O(n + m + k).


Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

O(n log log k)

We consider the complexity of computing a longest increasing subsequence parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers {1, 2, . . . , n} can be computed in time O(n log log k) in the RAM model, improving the previous 30-year bound of O(n log log n). The optimality of the new bound is an open question. queue

LONGEST INCREASING SUBSEQUENCE

We consider the problem of extracting a longest increasing subsequence (LIS) from a sequence multiple occurrences of integers between 1 and n in the sequence of length n does not change the result (see Section 4).

The question is related to the representation of permutations, elements of the symmetric group on {1, 2, . . . , n}, with Young tableaux. This is certainly why it has attracted a lot of attention. See the chapter by Lascoux, Leclerc, and Thibon in [START_REF] Lothaire | Algebraic Combinatorics on Words. Number 90 in Encyclopedia of Mathematics and its Applications[END_REF]Chapter 5] for a presentation of Schensted's algorithm [START_REF] Schensted | Largest increasing and decreasing subsequences[END_REF] in this context.

The question is also related to the computation of a longest common subsequence (LCS) of two strings, and to their alignment, in at least two ways. First, the LIS of S is the LCS between S and the sequence (1, 2, . . . , n). This remark leads to an O(n 2 ) running time algorithm implementing the standard dynamic programming technique used for finding longest common subsequences (it can indeed be reduced to O(n 2 / log n) [START_REF] Masek | A faster algorithm for computing string edit distances[END_REF][START_REF] Crochemore | A sub-quadratic sequence alignment algorithm for unrestricted cost matrices[END_REF]). Though simple, this solution cannot compete against direct computations. Second, the LIS question is involved in the solution to whole-genome comparisons proposed by Delcher et al [START_REF] Delcher | Alignment of whole genomes[END_REF] and in its subsequent variants. A comparison is based on maximal exact matches between the two input genome sequences, matches that are additionally constrained to occur only once in each sequence. An LIS is used to extract a long subsequence of matches that are compatible between each other, i.e. they appear in the same order along the two sequences, for producing an alignment of the complete genomes.

There is an extensive literature about the distribution of the maximal length of increasing subsequences in random permutations. As a notable result, it is known that the expected LIS length is ∼ 2 √ n as n → ∞. See [START_REF] Steele | Variations on the monotone subsequence theme of Erd ös and Szekeres[END_REF], or the survey by Odlyzko and Rains [START_REF] Odlyzko | On longest increasing subsequences in random permutations[END_REF] who discuss these questions, and references therein. of integers. The sequence S is assumed to be a permutation of the set {1, 2, . . . , n}, but having Liben-Nowell et al. [START_REF] Liben-Nowell | Finding longest increasing and common subsequences in streaming data[END_REF] explore the LIS problem in the streaming model which typically aims at reducing to a polylogarithmic amount the memory space required by the computation, in addition to efficient running time (see also [START_REF] Muthukrishnan | Data Streams: Algorithms and Applications[END_REF]).

A direct solution to computing a longest increasing subsequence, running in O(n log n) time, was proposed by Fredman [START_REF] Fredman | On computing the length of longest increasing subsequences[END_REF]. The solution is optimal if the elements are drawn from an arbitrary set due to the Ω(n log n) lower bound for sorting n elements. Parameterised by the LIS length k, the running time is O(n log k). On integer alphabets, the fastest known solution runs in O(n log log n) time (see [START_REF] Yang | A fast algorithm for computing a longest increasing subsequence[END_REF] and references therein). It relies on the priority search trees of van Emde Boas [START_REF] Van Emde | Preserving order in a forest in less than logarithmic time and linear space[END_REF][START_REF] Van Emde Boas | Design and implementation of an efficient priority queue[END_REF], which provide O(log log n) amortised time per operation when keys are drawn from the set {1, 2, . . . , n}.

The solution presented in this paper breaks the long-standing O(n log log n) upper bound down to O(n log log k), where k is the maximal length of increasing subsequences. It extends immediately to the computation of a longest increasing subsequence (not only its length). We assume the RAM model for evaluating the running time and the algorithm can be viewed as a parameterised solution (k is the length of the output). This is certainly a result mostly of theoretical nature but it opens the road to a possible linear-time LIS computation.

To get the O(n log log k) bound, we feed the priority queue used in the standard algorithm with elements drawn from a restricted range. This is done through a series of careful renamings of the elements. Downsizing the key universe to size O(k) leads the priority queue to work in amortised time O(log log k) and yields the announced result. But the length k of a longest increasing subsequence is not an input of the algorithm: we show that an approximation of it is enough, and how to compute such an approximation. Section 2 recalls the core algorithm for computing a longest increasing subsequence and Section 3 describes our improved solution.

CORE ALGORITHM

We recall the core algorithm for computing a longest increasing subsequence, starting with the computation of its length.

Let π be a permutation of {1, 2, . . . , n}. The aim is to extract a longest increasing subsequence from the sequence S = (π(1), π(2), . . . , π(n)).

Elements are processed in the order π(1), π(2), . . . , π(n). Conceptually we compute, for each length ℓ = 1, 2, . ., the smallest last element that can end an increasing subsequence of that length. It is called the best element for that length and denoted by B[ℓ].

Note that best elements B [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF], B [START_REF] Crochemore | A sub-quadratic sequence alignment algorithm for unrestricted cost matrices[END_REF], . . . , form an increasing sequence. This fact is used for the choice of a data structure to implement the list and is essential for getting an efficient computation.

One step in the algorithm is as follows (see [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF]). The currently processed element π(i) can extend any increasing subsequence having the last element smaller than it. If π(i) is larger than all the best elements computed so far for the sequence (π(1), π(2), . . . , π(i -1)), it produces an increasing subsequence longer than any previous one, for which it is the last element. Otherwise, π(i) becomes the best element for an existing length: it replaces the smallest element greater than it in B. This leads to the next algorithm to compute the maximal length of increasing subsequences of S, in which B is a priority queue that stores the best elements.

LIS(π, n) 1. B ←-(); k ←-0 2. for i ←-1 to n 3. x ←-π(i) 4.
Insert(B, x) 5.

if succ(B, x) exists Delete(B, succ(B, x)) 7.

else k ←-k + 1 7. return k Example Let S 0 = (12, 8, 9, 1, 11, 6, 7, 2, 10, 4, 5, 3). The queue B is initially empty. Its contents after processing sequentially each of the elements are successively: [START_REF] Schensted | Largest increasing and decreasing subsequences[END_REF], ( 8), [START_REF] Lothaire | Algebraic Combinatorics on Words. Number 90 in Encyclopedia of Mathematics and its Applications[END_REF][START_REF] Masek | A faster algorithm for computing string edit distances[END_REF], [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF][START_REF] Masek | A faster algorithm for computing string edit distances[END_REF], [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF][START_REF] Masek | A faster algorithm for computing string edit distances[END_REF][START_REF] Odlyzko | On longest increasing subsequences in random permutations[END_REF], [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF][START_REF] Hunt | A fast algorithm for computing longest increasing subsequences[END_REF][START_REF] Odlyzko | On longest increasing subsequences in random permutations[END_REF], [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF][START_REF] Hunt | A fast algorithm for computing longest increasing subsequences[END_REF][START_REF] Liben-Nowell | Finding longest increasing and common subsequences in streaming data[END_REF], [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF][START_REF] Crochemore | A sub-quadratic sequence alignment algorithm for unrestricted cost matrices[END_REF][START_REF] Liben-Nowell | Finding longest increasing and common subsequences in streaming data[END_REF], [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF][START_REF] Crochemore | A sub-quadratic sequence alignment algorithm for unrestricted cost matrices[END_REF][START_REF] Liben-Nowell | Finding longest increasing and common subsequences in streaming data[END_REF][START_REF] Muthukrishnan | Data Streams: Algorithms and Applications[END_REF], [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF][START_REF] Crochemore | A sub-quadratic sequence alignment algorithm for unrestricted cost matrices[END_REF][START_REF] Fredman | On computing the length of longest increasing subsequences[END_REF][START_REF] Muthukrishnan | Data Streams: Algorithms and Applications[END_REF], [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF][START_REF] Crochemore | A sub-quadratic sequence alignment algorithm for unrestricted cost matrices[END_REF][START_REF] Fredman | On computing the length of longest increasing subsequences[END_REF][START_REF] Han | Deterministic sorting in o(n log log n) time and linear space[END_REF], [START_REF] Bespamyathnikh | Enumerating longest increasing subsequences and patience sorting[END_REF][START_REF] Crochemore | A sub-quadratic sequence alignment algorithm for unrestricted cost matrices[END_REF][START_REF] Delcher | Alignment of whole genomes[END_REF][START_REF] Han | Deterministic sorting in o(n log log n) time and linear space[END_REF]. The length of an LIS is then 4 the size of B at the end of the run.

Computing a longest increasing subsequence (not just its length) is a simple extension of the algorithm. Instead of storing best elements only in the queue B, it suffices to store pairs of the form (x, y) where y is a best element predecessor of x. Then, tracing back predecessor information from the last best element in B produces a longest increasing subsequence.

Example (continued)

The predecessor of 5 when it was inserted in B was 4, that of 4 was 2, that of 2 was 1, which gives the LIS: (1, 2, 4, 5) of S 0 = (12, 8, 9, 1, 11, 6, 7, 2, 10, 4, 5, 3). Considering value 10, which is also a best element for an increasing subsequence of length 4, we get in the same way another LIS: (1, 6, 7, 10).

The running time of the algorithm relies mainly on the implementation of the queue B of best elements. Using an array and binary search (since elements are naturally sorted) to locate the position of the next element x (i.e. to implement the operations Insert, Delete, prev , and succ) yields a O(n log n) running time algorithm [START_REF] Fredman | On computing the length of longest increasing subsequences[END_REF].

Using a more sophisticated priority list implementation in the form of van Emde Boas trees [START_REF] Van Emde | Preserving order in a forest in less than logarithmic time and linear space[END_REF][START_REF] Van Emde Boas | Design and implementation of an efficient priority queue[END_REF], each step can be performed in O(log log n) amortised time yielding an overall O(n log log n) running time algorithm [START_REF] Hunt | A fast algorithm for computing longest increasing subsequences[END_REF].

In the next section we keep the same algorithm and the same priority list implementation but process the initial sequence differently to get the announced running time.

IMPROVEMENT BY RENAMING

In order to compute a longest increasing subsequence, having length k, from the sequence S of length n in time O(n log log k) we want a priority queue that works in O(log log k) amortised time per operation. Our strategy to get this result is to downsize the key universe of the queue to size O(k). This is done through a series of careful renamings of the elements of the sequence.

We assume that a good approximation m of k, m ≥ k, is given. We discuss how to find such an m at the end of the section.

The solution splits the initial sequence S into blocks of size m (except of course the last block that can be smaller), and processes each block separately in the order of the sequence. We discuss these two points.

Splitting S into blocks and sorting them. The sequence S is split into blocks, C j , j = 1, . . . , ⌈n/m⌉, of consecutive elements:

C j = (π((j -1)m + 1), π((j -1)m + 2), . . . , π((j -1)m + m)).
We also consider sorted blocks: C s j is the sorted list of elements of C j . Sorted and unsorted blocks are kept in memory.

Processing the third block. Queue B = (a, b, d) corresponds to the list of elements (1, 2, 7). It is merged with C s 3 producing the list (1, 2, 3, 4, 5, 7, 10). The content of B is update to (a, b, f). After processing keys g, d, e, c of elements of C 3 , the contents of queue B are successively: (a, b, f, g), (a, b, d, g), (a, b, d, e), and (a, b, c, e).

The list of elements whose keys are in B is: (1, 2, 3, 5), which give an LIS of length 4 ending with 5. Computing an LIS can be done as explained above.

In the implementation of Algorithm LIS, the cost of all renamings is O(n) if radix sorting is used. Each operation on the queue (Insert, Delete, Update) takes only O(log log m) amortised time because the elements in B belong to the set {1, 2, . . . , 2m}. This gives the following statement.

Lemma 1

The implementation of Algorithm LIS with blocks of size m, m ≥ k, and renamings runs in time O(n log log m) for a sequence of length n.

Finding the size of blocks. In the above presentation an approximation m of the length k of longest increasing subsequences of S satisfying m ≥ k, is assumed to be given. We discuss now how to find it.

The idea is to try increasing values of m until we get the approximation leading to the announced running time. Starting with some value m 0 , expected to be no more than k, for m (for instance, m 0 = 4), we consider the sequence (m i | i ≥ 0) defined by m i = m i-1 log mi-1 for i > 0.

For a given value of m in the sequence, we run Algorithm LIS implemented as described above but with this change: the run stops if the size of the queue B becomes larger than m, and the algorithm signals the fact. Therefore, the first time the algorithm does not stop due to this condition is when the value of m is the smallest value in the list that is larger than k. Let m i be this value. Doing so, the running time of the modified Algorithm LIS is O(n log log m j ) for 0 ≤ j < i because during all these runs the queue B contains no more than m j elements that all belong to {1, 2, . . . , 2m j }. For the value m i the run finishes normally because the condition of its complete execution, m ≥ k, is met. The running time for this value of m is O(n log log m i ).

Noting that log log(m log m ) = 2 log log m, the total running of the whole execution of Algorithm LIS for m = m 0 , m 1 , . . . , m i is O(n(Σ j=0,...,i 1/2 j-1 ) log log m i ),

which is also O(n log log m i ), and eventually O(n log log k) because m < k log k implies log log m < 2 log log k.

The conclusion lies in the next statement.

Theorem 2 Let S be a permutation of the integers {1, 2, . . . , n} and let k be the maximal length of its increasing subsequences. Computing k and extracting a longest increasing subsequence from S can be done in time O(n log log k).

CONCLUSION

The result stated in Theorem 2 is valid for sequences of integers with repetitions. Although the problem seems more general its solution comes down to that of a permutation as follows: each element x occurring at position i in S is renamed as the rank of the pair (x, i) in the lexicographically sorted list of all these pairs. This process is yet similar to the renaming by ranking used in our solution.

As to whether the upper bound in Theorem 2 is optimal, and not linear, raises the question of finding a totally different approach to compute longest increasing subsequences because the implementation of Schensted's algorithm is squeezed as much as possible with the present solution. But this is unlikely to happen if we consider that many researchers have already worked on the problem.

Another possible way for exploring the complexity of the problem is to use other techniques for sorting integers (see for example [START_REF] Han | Deterministic sorting in o(n log log n) time and linear space[END_REF]). But some of them are affiliated to van Emde Boas' method and are mostly designed to avoid the non-linear space coming from the large range of input integers. This is not the problem we have for computing the LIS of a permutation, though the techniques might simplify the solution or give a direct answer to the question.

Computing a longest increasing

  subsequence of length k in time O(n log log k) BCS International Academic Conference 2008 -Visions of Computer Science 6.

Computing a longest increasing subsequence of length k in time O(n log log k) BCS International Academic Conference 2008 -Visions of Computer Science

ACKNOWLEDGEMENTS

We are grateful to the anonymous reviewer for very detailed comments and for pointing reference [5] to us.

Sorting all the blocks individually by radix sort would take too much time because the elements in a given block are not in a limited range. To sort them all in linear time, we sort them altogether but identify the block of each element. To do so, we associate with each element π(i) the pair (⌈i/m⌉, π(i)) composed of its block number and itself. Pairs are then sorted lexicographically using radix sort. And since the first component of each pair identifies its block, we get all the blocks sorted.

The whole procedure runs in time O(n) because the elements and the block numbers are in the set {1, 2, . . . , n}.

Processing a block. In the modified algorithm, instead of processing an element x of S as in Lines 4-7 of Algorithm LIS, we deal with a key associated with it. All the elements of a block are treated online. Before going to the next block some work as to be done to assign keys to elements.

When processing a block, each element x is associated a key y = key(x) in a one-toone correspondence. The inverse function is called elt , then x = elt (y). Keys are in the set {1, 2, . . . , 2m} and are inserted in the queue B.

To assign keys in the designated range we merge elements whose keys are in the queue B with the current sorted block. Note that elements whose keys are in B are in increasing order as already mentioned in Section 2, which is essential for merging. Keys are then ranks of elements in the obtained sorted list. Since we assume m ≥ k, the number of keys in B is no more than m, the length of the sorted list is no more than 2m, which implies that keys are in the set {1, 2, . . . , 2m}.

After keys are assigned, we update B with the new keys of elements that are conceptually in the queue.

The last step in the treatment of a block is to process all its elements in the order of the block. The key of each element is dealt with as in Algorithm LIS.

The next scheme summarise the processing of a block.


Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Alessandra Gabriele

Filippo Mignosi
email: mignosi@ns.di.univaq.it

Mauriana Pesaresi
email: pesaresi@di.unipi.it

On the Longest Common Factor Problem

 who uses a famous constant-time solution to the Lowest Common Ancestor (LCA) problem in trees coupled with use of suffix trees. A data structure for the LCA problem, although linear in space and construction time, introduces a multiplicative constant in both space and time that reduces the range of applications in many biological applications.

In this article we present a new method for solving the LCF problem using the suffix tree structure with an auxiliary array that take space O(n). Our algorithm works in time O(n log a), where n is the total input size and a is the size of the alphabet. We also consider a different version of our algorithm that applies to DAWGs. In this case, we prove that the algorithm works in both time and space proportional to data DAWG's size.

Introduction

In 1976 E.M.McCreight settled a Kunt's open problem by introducing a new data structure on string: the Suffix Tree. Since then, many other problems have been settled by using suffix trees or similar structures such as Patricia trees, DAWG, CDAWG and suffix array (cf. for instance [START_REF] Apostolico | The myriad virtues of suffix trees[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF][START_REF] Grossi | Suffix trees and their applications in string algorithms[END_REF][START_REF] Crochemore | Algorithmique du texte[END_REF][START_REF] Maas | Matching statistics: efficient computation and a new practical algorithm for the multiple common substring problem[END_REF] and references therein). Some other applications can be retrieved by exploring the "Pattern Matching Pointers" maintained by S. Lonardi (cf. [13]).

The most commonly used data structures are Suffix Trees, Suffix Arrays, DAWGs, and CDAWGs. Usually any problem that can be settled by the aid of one of such data structure can also be settled by using any of the other ones. Despite this fact the passage from one data structure to another is not automatic nor always easy and, in some rare cases, not yet proved (see [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF] for example). Each of these structures has some advantage and some disadvantage. Some relation among the data structures and their size is reported in [3]. The size of an implementation of the above data structures is often evaluated by the average number of bytes necessary to store one letter of the original text. It is commonly admitted that these ratios are 4 for suffix arrays, 9 to 11 for suffix trees, and 5 for CDAWGs (cf. [3] for further information).

This paper deals with particular data structures: DAWGs. The problem we consider is reported by D. Gusfield, [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF]Sec. 7.6,9.4]. Given a set of m strings, for any k = 2, .., m find the longest factors that are common to at least k strings. The word common in the exact case means occurring with equality. The first solution in the exact case has been given by Hui, ( [START_REF] Hui | Color set size problem with applications to string matching[END_REF], [START_REF] Hui | A practical algorithm to find longest common substring in linear time[END_REF]). who uses a famous constant-time solution to the Lowest Common Ancestor (LCA) problem in trees coupled with the use of suffix trees (see [START_REF] Harel | Fast algorithms for finding nearest common ancestors[END_REF]16,[START_REF] Fischer | Theoretical and practical improvements on the rmqproblem, with applications to lca and lce[END_REF]). A data structure for the LCA, although it is linear in space and time, introduces a multiplicative constant in both space and time that reduces the range of applications in many biological applications.

Since DAWGs and CDAWGs are not trees, this solution cannot be used for the structures we are interested in. Therefore we look for a totally new solution. So, our solution turns out to be simpler and more efficient than Hui's one of about one order of magnitude. This solution is an extension from that of suffix trees to DAWGs.

This paper is organized as follows. In the next section we describe our solution for the problem based on the use of suffix trees, while in the Section 3 we extend our solution to DAWGs. The fourth section contains our conclusions and some conjectures on the approximate case of the problem. Hence in the Appendixes A and B, we report the specialized pseudo-code related to the procedures used in our algorithm.

A Simpler Solution

We assume the reader familiar with suffix trees and Generalized Suffix Trees.

Let S be a set of input strings S i , 1 ≤ i ≤ m, on the alphabet {0, 1}. Let u be the word composed of the concatenated labels of transitions along the unique path from the root to the node p in the Generalized Suffix Tree.

We want to compute a table ℓ having m -1 entries: where entry ℓ[k] provides the length of the longest factor common to at least k of the input strings and also points to one of the common factors having that length.

Our preprocessing is as follows. We build the Generalized Suffix Tree for the m strings. Then perform a depth-traversal of the tree and put all nodes in a stack in the order they appear. Define s to be an array of pointers representing the input strings useful to increase the algorithm's performances.

Each node stores the following information:

i represents the string identifier whose suffix is the node path-label. If this is not a suffix, this field is empty. -num is the number of distinct string identifiers that appear at the leaves in the subtree rooted in p. Observe that this approach is the same as the one used by Gusfield in [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF]Sec.7.6]. The difference lays in how to compute these values, that he calls C[p].

So we must first compute the num values and then we use them to update the table.

Computing the num values

For each node p, we create an auxiliary node size that stores the values num(p) and points to the strings it represents in s.

When for the vertex p we have num(p) = b, this means that in its subtree there are nodes representing suffixes from b different input strings. In other words, p is the common factors of exactly b different input strings. In the algorithm we call these nodes representative in the operation of U nion that plays an important role in the computing of our values.

The operation U nion is the union between disjoint sets of elements that, in our case, are nodes size linked to visited nodes. All pointers to auxiliary node of smaller size must point to the other node size and, naturally, we must also update the sizes of the involved nodes, i.e. the field num.

U nion operates as follows. Let a be a node with num(a) = 2 and let b with num(b) = 3. When we visit the a and b's father p, we execute a U nion of his children. The result is that num(p) = 5 and the p's label becomes a common factor of 5 input strings.

We keep the disjoint strings sets as follows. We use an array s of m pointers that represent the input strings and for which s[i] points permanently to the last met factor of the string s i . Since the last factor of a string is unique, the sets to merge are always disjoints.

In the algorithm we use three procedures called N odeSize T est, String T est and U nion (that implements the union's operation). Now we explain how they work, while in the Appendix A we show the code of them.

-N odeSize T est procedure: we check if the node size is already created. If not, we create it. -String T est procedure: when we visit a new node, we must update the information about the last visited factor of some string. Note that after this test and related "cut-append" of pointers, node size stores the current num value, while the internal node stores the real one. Because nodes size are representatives in the U nion, then they must be updated in every time. In Figure 1 we show the effect of this test. -U nion: after we have found the smallest son its pointer is redirected to the largest one, the num value is updated, and the new node size resulting from the merging is merged with the father node size. Then the node C is traversed. Therefore it's a leaf node representing the string s 2 , then the algorithm "cut" the pointer from B's node size to the element s [START_REF] Apostolico | The myriad virtues of suffix trees[END_REF], appending it to C's node size. In fact, the last factor of s 2 is the path-label of C. Observe that the values about the size of the nodes are updated during this test.

Now we describe the algorithm to compute in an efficient way the num information.

CountNum (stack, s)

1. while (stack isNotEmpty) do 2. p = pop(stack); 3.

N odeSize test; 4.

String test; 5.

if p has sons then 6.

U nion operation; 7. End CountNum.

The method

Once the num values are known and the string-depth of every node is known, the desired ℓ(k) values can be easily found with a linear-time traversal of GST (S).

When encountering a node p with num(p) = k, we compare the string-depth of p to the current value of ℓ(k). If the first value is greater than the second, we change ℓ(k) to the depth of p and update its pointer to the node representing the factor with the current value of ℓ(k).

Eventually, the resulting table holds the desired ℓ(k) values.

Time and space analysis

Building GST (S) requires linear space and time in the size of input [8, Sec.

6.4], O(n) with n = |S 1 | + • • • + |S m |. Algorithm CountN um executes a single
post-order traversal of GST (S) and its main operation is the U nion. Since the operation "cut-append" of a pointer from a node to another is done in constant time, then we have to know how many pointers could be involved during it.

Theorem 1.

[CountingNum] During the execution of CountN um(S, s) algorithm, the number of "cut-append" operations is less than n,

with n = |S 1 | + • • • + |S m | = |S|.
Proof. The statement is proved by induction on the total size n of the representatives u of the nodes p. Recall that u is p's representative if it is the concatenated labels of transitions of the unique path from the root to the node p in GST (S).

Basic step: let m be the minimal size of S. The root points directly to the m leaves. Therefore the number of "cut-append" operations is equal to m -1: we append all auxiliary leaves to the root. Since the input's size is equal to m then our thesis is proved. Inductive step: by induction we suppose that our thesis is true for every tree with representatives' size equal to n -1.

We prove the thesis is true at the level n.

Let our visit be stopped in a node with two sons. The first subtree has N L 1 leaves and representatives' size equal to n 1 , while the second has N L 2 leaves and size equal to n 2 .

When we get to the bottom level n, we add a character to every representative for each leaf. So the total representatives' size of the level n is equal to

n 1 + N L 1 + n 2 + N L 2 .
The U nion simply appends all leaves of one subtree to the other subtree.

cut -append = N L 1 + N L 2 < < n 1 + N L 1 + n 2 + N L 2 = n. (1)
When we visit the GST (S)'s root, the total representative's size is equal to the input length, n. Hence, the total number of U nion operations is linear in the input length.

During a run of the algorithm O(n) "cut-append" operations are executed, each of which takes constant time, so the overall U nion takes O(n) time.

Hence only O(n) time is needed to execute the algorithm and to compute all num numbers. Once these are known, only O(n) additional time is needed to build the output table.

Hui's solution take O(mn) time because it uses an array of k elements for each node of the tree to calculate the num values. We solve the original problem simply using O(m+n) space, because the algorithm makes use of a unique array. In this section we deal with the data structures that plays an important role in this paper, the Generalized Directed Acylic Word Graph (Generalized DAWG). We assume the reader familiar with DAWGs. Now we recall the definition of DAWG. Let S be our input set of strings. We want to analyse the meaning of the state u in terms of "representative". In DAW G(S) there are more edges entering the same state than in the corresponding tree, according to Def.1. So we define the representative of a state as the longest path from the initial state to it.

Like for Suffix Trees, we want to compute a table that gives for entry k the length of a longest factor common to at least k strings and also points to it. Now our preprocessing is less easy than in the previous section because more paths are not distinct. We build a Generalized DAWG for the m input strings. Each final state represents an input string (e.g., s i ) and is marked with a non null identifier (e.g., i).

Observe that in a DAWG two or more outgoing edges from the same state could finish in the same state and so we would like that the path from an internal state to other one is unique. Hence we keep only the representative of a factor's class. Since to solve the LCF Problem we need the longest labels of the paths, we keep only the transitions with the longest labels and we delete all other ones that have the same origin and target states. In this way the number of transition is drastically reduced and we obtain a pruned DAWG, denoted by D, having a deterministic transition function between adjacent states. Now we are ready to perform a particular breadth-traversal of the new structure to store all states in a stack, in a way that is similar to the procedure done on suffix trees. We put nodes in the stack in the order they appear. Our problem is that we traverse some nodes more times and we must store them only once. Hence, if a node is already stored, we delete its previous occurrences, we put its new occurrence and we increase a counter related to the node. Define s to be an array of pointers representing the input strings like above. In our data structure each state stores the following informations:

i is the string identifier whose suffix is the state path-label, -num is the number of distinct string identifiers that appear in the subgraph rooted in the state, -count is the counter mentioned above.

As in the previous section, we first compute the num values and then we use them to update the output's table.

How to compute desired values?

The algorithm to calculate num is almost the same as for suffix trees. The only difference is in the String T est procedure, because here there is another parameter to check, the count value. In the algorithm we use three procedures called N odeSize T est procedure, StringD T est procedure and U nionD. N odeSize T est procedure has already been described in the previous section. Now we explain how the StringD test works, while in the Appendix B we show its code and the U nionD one. First we perform the following test on the field count of the sons of the current state:

if count is not null for some son, we decrease the value of count and we "cut" only the pointer from array s to the previous state to link it to the actual node, because this one represents the last factor of the interesting string. Observe that we delete a node size when count become null. So, for count times we must replace the node size. This fact causes an additional extra-space but it permits to perform the execution in linear time; -otherwise we call the classical String test.

The complete algorithm is the following:

CountNumBIS (stack, s)
1. while (stack isNotEmpty) do 2. p = pop(stack); 3.

N odeSize test; 4.

StringD test; 5.

if p has sons then 6.

U nionD operation; 7. End CountNum.

Building the output table

Once the num value and the string-depth of every state are known, the desired ℓ(k) values can be easily found with a linear-time traversal of D.

When encountering a state p with num(p) = k, the string-depth of p is compared to the current value of ℓ(k) and if the first one is greater than the second, ℓ(k) is changed to the depth of p and its pointer updated to the node representing the factor with the current value of ℓ(k).

Finally the resulting table holds the desired ℓ(k) values. Visiting the state G is the same as visiting the corresponding tree node. When we traverse state F , we create a duplicate pointer to s [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF] not to lose the information related to state G: in fact, two other edges arrive in this state and they need to know that G is a suffix of s [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF]. Note that the field count of state G is decreased. Therefore F is also a suffix of s [START_REF] Apostolico | The myriad virtues of suffix trees[END_REF], then we perform a traditional U nion. The same happens when traversing states L and B. In last case, since the field count of state G is null, then we can delete its node size because we have visited all its neighbors.

Time analysis

Let n the input size, with

n = |S 1 | + • • • + |S m |.
Building DAW G(S) requires linear time in the input size as described in [START_REF] Inenaga | On-line construction of compact directed acyclic word graphs[END_REF]. Algorithm CountN umBIS executes a single traversal of D and its main operation is U nion. Since the operation "cut-append" of a pointer from a node to another is constant, then we would like to know how many pointers could be involved during it.

Let D be the Generalized DAW G over S. We can use a breadth-first visit of D to re-create the original Suffix Tree. Each path from initial state to a final state in DAW G is used to build a path from the root to a leaf in the Suffix Tree. Note that the technique is the same as McCreight's one (cf. [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF]) to create suffix trees directly from input's strings.

After this traversal, we have created a suffix tree with a number ns of nodes that is larger than the number nc of DAW G states, with same edges and related labels. Hence representatives of suffix tree states are the same as that of DAW Gs.

Since nc ≤ ns, from Theorem 1, we have the following result:

Theorem 3. [LCSS Counting Bis] During the execution of CountN umBIS(S, s) algorithm, the number of "cut-append" operations is less than n, with n

= |S 1 | + • • • + |S m | = |S|.
During the run of the algorithm there are O(n) "cut-append" operations executed, each of which takes constant time, so all U nion executions take O(n) time in total.

Hence only O(n) time is needed to execute the algorithm and to compute all num S numbers. Once these are known, only O(n) additional time is needed to build the output table.

Conclusions

Recent experiments [START_REF] Crochemore | On the suffix automaton with mismatches[END_REF] have showed that DAWGs are space thrifty not only in exact problems, but also in the approximate cases, where some "errors" or "faults" are allowed. To build the approximate DAWG of a word in optimal time remains an open problem. Now, we think that our solution of exact problem can be applied to these data structures to solve the approximate one. If the conjecture reported in [START_REF] Crochemore | On the suffix automaton with mismatches[END_REF] is true and if it possible to build approximate DAWGs in optimal time, then our solution will drastically outperform previous solutions.

A Appendix

Now we detail the procedures used by the algorithm for Suffix Tree. Recall the data structures in a formally way. The auxiliary structure s is an m-array of pointers. The node of GST (S) are formed by three fields (and not two):

the fields i and num; -the field ns is a pointer to the node size related to our node.

The node size has two fields (and not one):

the field num; -the field ns is a set of pointers to the structures s, one for each string that the node representing.

B Appendix

Now we detail the procedures used by the algorithm for DAWG. Recall the data structures in a formally way. The auxiliary structure s is an m-array of pointers. The node of DAW G(S) are formed by four fields (and not three):

the fields i, num and count; -the field ns is a pointer to the node size related to our node.

The node size has two fields (and not one):

the field num;

the field ns is a set of pointers to the structures s, one for each string that the node representing.

Fig. 1 :

 1 Fig.1:In the left figure, is shown the situation after the visit of the B node, at the top of the stack. It's the common factor of all input strings. Then the node C is traversed. Therefore it's a leaf node representing the string s 2 , then the algorithm "cut" the pointer from B's node size to the element s[START_REF] Apostolico | The myriad virtues of suffix trees[END_REF], appending it to C's node size. In fact, the last factor of s 2 is the path-label of C. Observe that the values about the size of the nodes are updated during this test.

Theorem 2 .

 2 The Lowest Common Factor Problem on a set of m input's strings, represented by a Generalized Suffix Tree, can be solved in O(n) time, with n = |s 1 | + • • • + |s m |, and O(m + n) space.

Fig. 2 :

 2 Fig.2: How StringD works. Visiting the state G is the same as visiting the corresponding tree node. When we traverse state F , we create a duplicate pointer to s[START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF] not to lose the information related to state G: in fact, two other edges arrive in this state and they need to know that G is a suffix of s[START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF]. Note that the field count of state G is decreased. Therefore F is also a suffix of s[START_REF] Apostolico | The myriad virtues of suffix trees[END_REF], then we perform a traditional U nion. The same happens when traversing states L and B. In last case, since the field count of state G is null, then we can delete its node size because we have visited all its neighbors.

Finally, we can state: Theorem 4 .

 4 The Lowest Common Factor Problem on a set of m input strings, represented by a Generalized Directed Acyclic Graph, can be in O(n) time, with n = |s 1 | + • • • + |s m |, and O(m + n) space.

  Definition 1. The DAWG for a set of strings s 1 , • • • , s m is a directed acyclic graph, with a node marked as initial and m distinct nodes F 1 , • • • , F m marked as final. Edges are labeled with non empty factors of at least one of the strings. Labels of two edges leaving the same node cannot begin with the same character. For every string s i in the set, all suffixes of s i are spelled by patterns starting at the initial node and ending at node F i . Paths ending at non final nodes correspond to strict classes of factors of the congruence relations ≡ Suf (S) .

  NodeSize test (GST (S), s) 1. if p.ns = N il then 2. p.ns =new node. 3. Return(GST (S), s). new node size m; 5. p.ns = merge(p.ns, m); 6. p.num = p.ns.num. 7. End U nion operation.

	String test (GST (S), s)
	1. for every i of p do
	2.	if p.i! = N il then
	3.	s[p.i].ns.num --
	4.	if s[p.i].ns.num = 0 then
	5.	delete s[p.i].ns;
	6.	s[p.i] = p;
	7.	p.ns.ns = s[p.i];
	8.	p.ns.num + +;
	9.	p.num + +.
	10. Return(GST (S), s).
	Union (GST (S), s)
	1. Merge between nodes size
	2.	merge between pointers to s;
	3.	sum between the fiels num;
	4.	have created a