Julien Allali
email: allali@univ-mlv.fr

Marie-France Sagot
email: sagot@inria.fr

The at most k-deep factor tree

Keywords: arbre des suffixes, arbre des facteurs, structure d suffix tree, at most k-deep factor tree, string index, pattern matching

Cet article présente un nouvelle structure d'indexation proche de l'arbre des suffixes. Cette structure indexe tous les facteurs de longueur au plus k d'une chaîne. La construction et la place mémoire sont linéaires en la longueur de la chaîne (comme l'arbre des suffixes). Cependant, pour des valeurs de k petites, l'arbre des facteurs présente un fort gain mémoire vis-à-vis de l'arbre des suffixes.

Introduction

The suffix tree is one of the best known structures in text algorithms. It is used in many fields such as string matching [START_REF] Crochemore | Text Algorithms[END_REF] [START_REF] Crochemore | Jewels of Stringology[END_REF], data compression [START_REF] Larsson | Structures of String Matching and Data Compression[END_REF][16], computational biology [START_REF] Brazma | Predicting gene regulatory elements in silico on a genomic scale[END_REF] [7] [START_REF] Marsan | Extracting structured motifs using a suffix tree -algorithms and application to promoter consensus identification[END_REF] [START_REF] Sagot | Spelling approximate repeated or common motifs using a suffix tree[END_REF] etc. A suffix tree indexes all suffixes of a string and can be constructed in time linear in the length of the string. Furthermore, the size and depth of the tree are also linear in the length of the string. The constant however may be big. One of the original implementations of a suffix tree [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF] thus requires 28 bits per input char. Numerous efforts have been made over the years to reduce this space. In particular, S. Kurtz proposed in [START_REF] Kurtz | Reducing the Space Requirement of Suffix Trees[END_REF] various implementations which require 20 bits per input char in the worst case and 10 on average. The same author with co-workers suggested in another paper [START_REF] Giegerich | Efficient Implementation of Lazy Suffix Trees[END_REF] a variant of the suffix tree, called the lazy suffix tree, which can be built on the fly as the need arises.

In many applications, the length of the patterns to be searched in the suffix tree can be limited. Typically, this concerns applications to motif extraction in biological sequences where the motifs of interest are often short or are composed of short parts at constrained distances from one another [START_REF] Vanet | Promoter sequences and algorithmical methods for identifying them[END_REF], applications to data compression using a sliding window [START_REF] Fiala | Data compression with finite windows[END_REF], [START_REF] Na | Data Compression with Truncated Suffix Trees[END_REF], etc.

There is therefore often no need to have the whole suffix tree. This is our motivation for proposing a new structure, called the at most k-deep factor tree, or, for short, the k-factor tree. The k-factor tree retains the linear properties of the suffix tree. Indeed, its construction follows closely that of the suffix tree as proposed by Ukkonen [START_REF] Ukkonen | On-line construction of suffix trees[END_REF]. For small values of k, there is furthermore a gain in time and space that may be important. The gain in time concerns both the construction itself and the use of the tree, for instance, to do pattern matching.

Since our construction of the k-factor tree is strongly based on Ukkonen's suffix tree construction, we start by recalling Ukkonen's algorithm in Section 2. We then introduce our own algorithm for the k-factor tree construction. The k-factor tree has been implemented using the coding proposed by Kurtz in [START_REF] Kurtz | Reducing the Space Requirement of Suffix Trees[END_REF] and the results of the experiments are discussed in Section 5.

Suffix trees

Before recalling Ukkonen's suffix tree construction, we start by introducing some notations.

Notations

In what follows, s will denote a string over a finite alphabet Σ whose cardinality is |Σ|. The length of s is |s|. A string s is therefore an element of the free monoid Σ * . The i th letter of s is denoted by s i and s i...j represents the factor s i s i+1 . . . s j (also named substring or subword). The suffix of s starting at position i is the factor s i...|s| . If s ends with a letter which is not in Σ, we say that s has an ending symbol, denoted by $. Given two strings u and v, we note u.v the concatenation of u with v.

Given a tree T with root R whose edges are labelled by elements of Σ * and a node N of T , path(N ) is the string corresponding to the concatenation of the labels encountered along the path from R to N . The depth of N , denoted by depth(N ), is the number of nodes between R and N , N included (depth(R) = 0).

Definition of a suffix tree

The suffix trie of s is a tree with edges labelled by elements of Σ. For each factor of s, there exists a node N such that path(N ) is equal to that factor. If the factor is a suffix of s, some SuffixTree(s) 1. Tree T 2. For i from 1 to |s| 3.

For j from 1 to i 4.

Add(T ,s j...i ) Figure 2: Naive algorithm of these nodes may be leaves. If s has an ending symbol, all nodes N whose path from R spells a suffix of s are leaves.

The implicit suffix tree of s is a tree with edges labelled by non-empty elements of Σ * . The tree is a compressed version of the suffix trie. Each internal node N of the suffix trie that has only one son is deleted and its two adjacent edges are replaced by an edge that goes from N 's father to N 's son. The label of the new edge is equal to the concatenation of the label of the edge going from N 's father to N and of the label of the edge from N to its son. This tree is called implicit because not all suffixes of s lead to a leaf. The true suffix tree is obtained when an ending symbol $ is added at the end of s.

Suffix tree construction

A first suffix tree construction algorithm of complexity linear in the length of the string was presented by Weiner in 1973 [START_REF] Weiner | Linear pattern matching algorithm[END_REF]. McCreight introduced a similar but more performing algorithm in 1976 [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF]. In 1995, Ukkonen published an on-line construction of the suffix tree using a very different approach [START_REF] Ukkonen | On-line construction of suffix trees[END_REF]. Later, Giegerich and Kurtz [START_REF] Giegerich | From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction[END_REF] showed how all three constructions are in fact similar.

We now briefly present Ukkonen's algorithm which is the basis for the k-factor tree construction. For more details, we refer the reader to the original paper [START_REF] Ukkonen | On-line construction of suffix trees[END_REF]. We follow here the description of the algorithm given in [START_REF] Gusfield | Algorithms on strings, trees and sequences: computer science and computational biology[END_REF].

Ukkonen's algorithm

The algorithm is divided into |s| phases. The i th (for 1 ≤ i ≤ |s|) phase consists in the insertion of all suffixes of s 1...i into the tree. Each phase i is then divided into j steps, one step for each insertion of a suffix of s 1...i (see Figure 2). This naive algorithm is clearly in O(|s| 3 ). We show now how Ukkonen obtains a linear complexity.

Cases met when inserting a word w in the tree

Let us call v the longest prefix of w which is already in the tree. We have w = vu. During the insertion of w, three cases may occur:

1. u is the empty word so that w is already in the tree: there is nothing to do.

2. spelling v from the root leads to a leaf: all we need to do is append u to the label of the edge leading to this leaf.

3. the last case may be divided into two subcases:

(a) spelling v leads to an internal node N : we attach a new leaf to this node; the edge from N to the leaf is labelled u.

(b) spelling v leads to the middle of an edge: we have to cut this edge at the position reached and insert a new node N ; to the node N thus created, we then attach a new leaf; the edge from N to the leaf is labelled u.

Suffix links

Suffix links are fundamental elements in all linear time suffix tree construction algorithms. We shall see later that they enable to reduce the cost of string insertion during the algorithm.

A suffix link is an oriented link between two internal nodes in the suffix tree. Given a node N , its suffix link points to the node, denoted by S l (N ), such that path(S l (N )) is equal to path(N ) 2...|path(N )| (that is, to path(N ) without the first letter). In other words, path(S l (N )) is the longest proper suffix of path(N ). All internal nodes have a suffix link.

Suffix links are added to the tree during construction as follows: let us suppose that, during the insertion of string s j...i , a node N is created to which a new leaf is attached (case 3b). We know that s j...i-1 is in the tree because we inserted it during the previous phase. We therefore have that path(N ) is equal to s j...i-1 . By construction, when a string is in the tree at the end of a phase, all suffixes of this string are also in the tree. The factor s j+1...i-1 is thus already in the tree. Two cases may then happen: the path labelled s j+1...i-1 ends in a node, let us denote it by N , or it ends inside an edge. In the second case, the insertion of factor s j+1...i leads to the creation of a node, that we also denote by N . In both cases, the suffix link of N points to N .

Fast insertion

Let N be the last node reached during the insertion of s j...i that has a suffix link. We have that s j...i is equal to path(N ).w.σ, where w can be empty and σ ∈ Σ. If S l (N ) is the root, then the insertion of s j+1...i is done naively. If S l (N ) is not the root, in order to insert s j+1...i , we just have to follow w from S l (N ) and add σ if necessary.

During the insertion described above, we found w in the tree by successively comparing each letter of w. In fact, we can avoid such comparisons in the following way. At each node met during the insertion, we just need to know which edge to take. Once this edge is identified, we can go directly to the node it points to and, as a consequence, move in w by possibly more than one letter.

The time spent during an insertion is essentially composed of the time needed to calculate the length of an edge plus the number of nodes traversed during the insertion. The next section shows how the length of an edge can be computed in constant time and how, simultaneously, the space required by the tree may be reduced. In the proof of the time linearity of the algorithm, we show that the overall number of nodes traversed is then O(|s|).

Edge coding

The labels of the edges can be coded by a pair of integers which denote, respectively, the start and end positions in s of the string labelling the edge. This allows to obtain a linear space occupancy for the tree as is detailed below. It also leads to an improvement in the time complexity of the suffix tree construction as leaves can then be automatically extended.

Automatic leaf extension and condition for ending a phase

Let us call end position of an edge the second value in the label of an edge, which corresponds to the end position of the string labelling that edge. Suppose a leaf is created during the insertion of s j...i . The end position of the edge pointing to this leaf is i. In the next phase, the insertion of s j...i+1 will lead to case 2, and the end position of the edge will now become i + 1, and so on for all the following phases. When a leaf L with edge E leading to it is created, we can then set the end position of E to a global variable whose value is the number of the phase. This will exempt us from having to make the insertions corresponding to the extension of all edges leading to a leaf. Furthermore, if the insertion of s j...i requires the creation of a leaf, then all strings s ...i for from 1 to j lead to a leaf in the tree. During the next phase, if the insertion of s j+1...i has not created a leaf, we can therefore start the insertion of the suffixes of s 1...i+1 from the insertion of s j+1...i+1 (that is, from step j + 1) because all the longer suffixes are implicitly inserted. Each phase then starts from the last leaf created.

In the same way, if, during the insertion of s j...i , we end up in case 1, we do not have to insert s ...i for from j + 1 to i because if s j...i is already in the tree, then all suffixes of s j...i are also in the tree.

In what follows, all non implicit insertions such as those described above are called explicit.

Algorithm

Figure 3 gives the complete algorithm for Ukkonen's construction. We see that index j does not appear anymore. As just showed, the beginning of each phase is deduced from the end of the previous phase, and the end of a phase is deduced from the result of a current insertion. Moreover, we may observe that the algorithm of Figure 3 constructs the implicit suffix tree of s. To obtain the suffix tree of s, an ending symbol $ must be appended to s.

Complexity

We now analyse the time and space complexities of the suffix tree construction. These will be the same for the k-factor tree.

Time complexity

Ukkonen's assertion [START_REF] Ukkonen | On-line construction of suffix trees[END_REF] that his suffix tree construction algorithm is linear in the length of the string rests upon the following lemma [START_REF] Gusfield | Algorithms on strings, trees and sequences: computer science and computational biology[END_REF]:

Lemma 1 Let N be a node. We have that depth(N ) ≤ depth(S l (N )) + 1.

The implicit leaf extensions inside a phase take constant time, so the implicit insertions made over the complete algorithm take O(|s|) time. The time taken by the explicit insertion of a string in the tree is directly related to the number of nodes traversed after the jump along the suffix link since the ascent from a node to its father and the jump along the suffix link can be done in constant time. Instead of counting the number of nodes traversed after the jump along the suffix link for each separate insertion, we can upper bound the number of nodes traversed during the whole construction. Let j be the index of the extension currently considered.

f orward ← length(F ather(lastLeaf ), lastLeaf) -1 7. if S l (F ather(lastLeaf )) is undefined and F ather(lastLeaf )! = R 8. f orward ← f orward + length(F ather(F ather(lastLeaf )), F ather(lastLeaf )) 9. if F ather(F ather(lastLeaf )) is R 10.
AddString(R,s,if orward + 1,i) AddString(S l (F ather(F ather(lastLeaf ))),s,if orward,i)

13. else 14. if F ather(lastLeaf ) is R 15. AddString(R,s,i -f orward + 1,i) 16. else 17.
AddString(S l (F ather(lastLeaf )),s,if orward,i)

18.
if a node was created during the previous step 19. set suffix link of this node to the last node reached during the insertion 20.

if a leaf was created in the call to AddString if a node was not created in the call to AddString Index j remains unchanged between two successives phases, and it never decreases. We may observe that we do at most 2|s| explicit insertions because we have |s| phases and j is at most |s|. During an explicit insertion, the depth of the node currently considered is first decreased by at most two, one to reach the father of a leaf and one when jumping along the suffix link, and then increased at each skip down the tree. Since the maximal depth of the tree is |s| and we do at most 2|s| insertions, the total number of nodes considered is O(|s|). If we suppose that the access to a child of a node is done in O(1) time, then the total time complexity of the suffix tree construction is in O(|s|).

Space complexity

Let T be the suffix tree of s. The root of T has exactly |Σ| + 1 children. One of them corresponds to a leaf (the string label of the edge leading to it is $). The worst case for the space complexity will be obtained if each internal node has exactly two children and each edge is labelled with a single letter (i.e. its length is one).

In that case, the total number of nodes whose depth is k in the tree is:

2 k-1 (|Σ| + 1) -2 k + 2 that is 2 k-1 (|Σ| -1) + 2.
The number of leaves in T is |s| + 1 and we can then deduce the depth d of T in the worst case which is:

2 d-1 (|Σ| -1) + 2 + d -1 = |s| + 1 that is 2 d-1 (|Σ| -1) + d = |s|
An upper bound for d is:

d max = log 2 2|s|
|Σ| -1 .

We can now compute the total number of nodes in T which is:

1 + k=dmax k=1 [2 k-1 (|Σ| -1) + 2] that is: 2|s| + 2d max -|Σ| + 2.

Factor trees

We now present the k-factor tree construction. A naive approach consists in building the suffix tree and then pruning the tree in such a way that for each node N of the remaining tree, |path(N )| ≤ k. Clearly, this approach does not improve the space complexity because it requires first constructing the suffix tree.

Recall that one of the main ideas behind Ukkonen's suffix tree construction is the automatic leaf extension allowed by the use of a global variable. We must be able to preserve this idea in the k-factor tree construction if we wish to keep the linear time complexity. Let us call length of a leaf L, the length of the string labelling the path from R to L. Preserving Ukkonen's idea requires finding a way of stopping the extensions when a leaf reaches the length k.

Construction

The k-factor tree contruction is based on Ukkonen's algorithm. It is divided into two parts:

• building the implicit suffix tree for s 1...k-1 ;

• adding to the tree all the suffixes of s i-k+1...i for i from k to |s|.

We now detail these two parts. Henceforward, we call end position of a leaf what corresponds to the end position of the edge leading to that leaf.

First part: construction of the implicit tree of the suffixes of s 1...k-1

The first part is done following Ukkonen's algorithm in a straightforward way. The only difference is that, when a leaf is created, it is now added to a queue called queue leaf .

Second part: construction of the implicit tree of the suffixes of s i-k+1...i for i from k to |s| For each string corresponding to a suffix of s i-k+1...i for i from k to |s| that needs to be inserted in the tree, we proceed essentially as in Ukkonen, that is, we go up to the last node which has a suffix link, jump along the suffix link and then go down in the tree. As for the first part, we add each newly created leaf to queue leaf . We now also have to remove an element from the head of the queue at the end of each phase. Furthermore, there may be another subtle but important difference in relation to Ukkonen's algorithm depending on the state of queue leaf at the beginning of a phase.

Indeed, in Ukkonen's suffix tree construction, a phase starts from the last leaf created. At the start of a phase i in our algorithm, two cases may happen:

• there is a leaf L at the end of queue leaf ;

• queue leaf is empty.

In the first case, we proceed with phase i straightforwardly from leaf L, which corresponds to the last leaf created.

In the case where queue leaf is empty, we do not proceed as in Ukkonen from the last leaf that was created in the algorithm, but from the last position reached in the tree during the previous phase. This position may be in the middle of an edge. The reason for this is the following. Let i be the phase for which queue leaf is empty when the phase begins and let L be the last leaf created before phase i. The leaf L corresponds therefore to s i-k...i-1 . At phase i, we would start from leaf L, jump up to L's father, along L's father suffix link and then try to insert s i-k+1...i . If s i-k+1...i were already in the tree, phase i would be terminated and phase i + 1 would start again from the leaf L. The first string needing to be inserted would be s i-k+2...i+1 and we would have to follow two suffix links from L's father in order to reach s i-k+2...i-1 and check for the existence of s i s i+1 at the end of s i-k+2...i-1 . If s i-k+2...i+1 were already in the tree, phase i + 1 would also be stopped, and phase i + 2 would again start from the leaf L and require now three suffix link jumps before trying for the insertion of the first suffix of the phase. If we proceeded in this way, we could no longer guarantee a linear complexity for the algorithm. This will not be the case if, instead, we start each phase for which queue leaf is empty at the last position reached in the tree during the previous phase. Inserting s i-k+1...i implies then just checking, from such a position, for the existence of s i , which can be done in constant time. If a leaf needs to be created, we create it, add it to queue leaf (it will become the head of the queue) and go to the next step of the phase. If a leaf L is reached (path(L) is thus already equal to s i-k+1...i ), we proceed with the next step of the phase. Any leaf that needs to be created during the phase is added to the queue.

At the end of phase i, the leaf L at the head of queue leaf is removed. The end position of L is set to i.

Lemma 2 Stopping the automatic extension:

For each phase i, k ≤ i ≤ |s|, if queue leaf is not empty let us call L the leaf at the head of queue leaf . The length of path(L) is equal to k at the end of phase i.

Proof. When a leaf is created in the suffix tree, its length is always equal to the length of the last created leaf minus one. This can be observed in Ukkonen's algorithm. Indeed, if in the phase i, we start with step j and we create a leaf L, it will be because during a previous phase , the insertion of s j-1... ended in the creation of a leaf L , while during phases + 1 . . . i -1 there was no leaf created. At the end of phase i -1, leaf L will have a length of i -(j -1) + 1 because of the automatic extensions. We then insert s j...i which creates leaf L whose length is equal to ij + 1. During the first phase, which is phase i = k, of the second part of the algorithm (when the suffixes of s i-k+1...i for i from k to |s| are inserted), the leaf L at the head of queue leaf is the one that was created during the insertion of s 1 . It was extended to k -1 during the first part of the algorithm. At the end of phase i = k, L is removed from the queue, its end position is set to i and thus its length is clearly k. If, at this point, any leaf remains in the queue, the length of the one at the head is k -1, and will become k at the end of the next phase (i + 1) when it is removed from the queue, and so on.

Suppose now that at the beginning of a phase i, queue leaf is empty. We start the phase by trying to insert s i-k+1...i . If this creates a leaf, it will be put in the queue and will be at the head of it. When the phase ends, the leaf will be removed and have length k. If no leaf is created in phase i, we proceed with phase i + 1 and apply the same reasoning. 2

Algorithm

The pseudo code for the first part of the k-factor tree construction algorithm is the same as for Ukkonen (Figure 3), we just have to add to queue leaf the leaf created in line 21. The pseudo code for the second part of the k-factor tree construction is given in Figure 5.

Factor Tree(R, s , k , queue leaf ) 1. For i from k to |s| 2.
endP hase = f alse 3.

if queue leaf is not empty if S l (F ather(lastLeaf )) is undefined and F ather(lastLeaf

)! = R 15.
f orward ← f orward + length(F ather(F ather(lastLeaf )), F ather(lastLeaf ))

16. if F ather(F ather(lastLeaf )) is R 17.
AddString(R,s,if orward + 1,i) AddString(S l (F ather(F ather(lastLeaf ))),s,if orward,i)

20. else 21. if F ather(lastLeaf ) is R 22.
AddString(R,s,if orward + 1,i) AddString(S l (F ather(lastLeaf )),s,if orward,i)

25.

if a node was created during the previous step 26.

set the suffix link of this node to the last node reached during the insertion 27.

if a leaf was created in the call to AddString while(not endP hase)

33.

remove the leaf at the head of queue leaf and set its end value to i 34. end for 35. return R

Complexity

We now analyse the time and space complexities of the k-factor tree.

Time complexity

The time taken by the construction of the k-factor tree is linear in the length of s. The proof is very similar to the one for Ukkonen's suffix tree construction presented in section 3.2. The first part of the algorithm requires O(k) time. Lemma 1 remains true for the k-factor tree. During the second part of the algorithm, we have |s|-k +1 phases. We can start by observing that all operations related to queue leaf are done in constant time and therefore take O(|s|-k) time for the whole algorithm. As in Ukkonen, between two phases, the start index j in s of the first substring of s that must be inserted can never decrease. The complexity thus still depends only on the total number of nodes encountered during all insertions. This number is at most 2|s| (we have |s|k + 1 phases and j is at most |s|). As the depth currently reached in the tree remains unchanged between two phases and we can go up by at most two nodes at each insertion, we can go up in the tree by at most 4|s| nodes only during the whole algorithm. Since the depth of the tree is at most k, the total number of nodes encountered is O(|s|).

If we make the assumption that the cost to reach the child of a node is constant (|Σ| is fixed), the whole algorithm therefore runs in linear time.

Space complexity

We now compute the number of nodes in the k-factor tree in the worst case. Clearly, the worst scenario corresponds to the case where each node has |Σ| children. The number of nodes is then =k =0 |Σ| , that is:

|Σ| k+1 -1 |Σ| -1 .
The total number of nodes in the worst case is therefore:

min( |Σ| k+1 -1 |Σ| -1 , 2|s| + 2 log 2 ( 2(|s| -1) |Σ| -1 ) -|Σ| + 2).
We can thus guarantee a gain in memory when k is less than log |Σ| (2(|Σ| -1)|s|) -1. This result has been confirmed in practice. Experiments are presented in the next section.

Coding and experiments

The construction algorithm we have just presented may be used with any currently existing coding of the suffix tree. We chose to use it with the coding adopted by S. Kurtz in [START_REF] Kurtz | Reducing the Space Requirement of Suffix Trees[END_REF] for building suffix trees. This employs an "Improved Linked List Implementation" and is called the illi coding. The choice is motivated by the fact that, to the best of our knowledge, this is the best implementation in practice which is currently available. We start by explaining the coding techniques adopted by S. Kurtz then describe the modifications or extensions we had to do to it in order to adapt the coding to the construction of k-deep factor tree. Basically, the coding must be changed so that it can efficiently handle the fact that a leaf in the factor tree may now store more than one position. We end by presenting some experimental results. The suffix tree of s = ABAAB$, the right tree shows the suffix tree as it is coded by illi.

Kurtz's coding

We briefly explain the illi coding. For further details, the reader is referred to [START_REF] Kurtz | Reducing the Space Requirement of Suffix Trees[END_REF].

The internal nodes and the leaves of the suffix tree are coded using two different tables. In both tables, the index of a node corresponds to the order in which the nodes are created during construction and thus put in the right table. In particular, the index of a leaf corresponds to the position in s of the suffix that is spelled by the path from the root to the leaf. In all cases, the children of a node are stored in a linked list (first-son, right-sibling). The coding for a node contains the following information:

• The node is an internal node N :

start position of the first occurrence of path(N ) in s that required the creation of a node (this corresponds to the first occurrence of path(N ) in s that is followed by a letter different from the one following all previous occurrences; possibly there is only one). Such position will be denoted by head(N );

-|path(N )|;
the first child of N ;

the right sibling of N ;

the suffix link of N .

• The node is a leaf F :

the right sibling of F .

Observe that this information is enough since the values of head(F ) and |path(F )| for a leaf F may be deduced directly from the index of the leaf in the table. Indeed, head(F ) is that index (of creation of the leaf F ) and |path(F )| = |s|head(F ).

Figure 6 presents a suffix tree coded according to illi. One of the main characteristics of the coding comes from the distinction between two types of nodes: the so-called Small and Large nodes. The idea is that nodes are created in batches, one batch (of possibly more than one node) inside each phase of the construction algorithm. During phase i (lines 12-32 in Figure 5), if z nodes are created, say N 1 , . . . , N z , then for each node N i , 1 ≤ i < z, we have that N i+1 is the node to which points the suffix link of N i (line 26), |path(N i )| = |path(N z )| + (zi) and head(N i ) = head(N z ) -(zi). The nodes N i for 1 ≤ i < z are the so-called Small Nodes and the node N z is the so-called Large Nodes. The coding of a Small Node will also include a field indicating the distance (i.e., the number of nodes) until the Large Node with which it is associated. This distance is equal to zi.

The coding is detailed now. As indicated in [START_REF] Kurtz | Reducing the Space Requirement of Suffix Trees[END_REF], the index of a leaf may be stored on 27 bits, that of an internal node on 28 bits. To code the index of any node, we thus need 29 bits, the first one indicating if the next 28 correspond to the index of a leaf or of an internal node.

A leaf F occupies 32 bits coded according to the model B shown below. The third bit (↓) indicates whether the sibling of F is nil. If this is the case, it is flagged and the next 29 bits code for the suffix link of the father (as explained below), otherwise the next 29 bits code for the sibling of F . We shall come back to the use of the first 2 bits later. The coding of a Small Node is done using 2 * 32 bits (models A and B above) and the coding of a Large Node on 4*32 bits (models A, B, C and D above). We denote by N the coded node, and by i its index in the table of nodes. The first 5 bits of A are zero if N is a Large Node and, if N is a Small Node, are equal to the distance until the Large Node with which N is associated. In the case where distance ≥ 32, a "dummy" Large Node is inserted at the index i + 32. The first child of N is stored on the last 27 bits of A and the first 2 bits of B. The remaining 30 bits code for the right sibling. If N is a Small Node, its coding is finished. Indeed, the suffix link, head(N ) and |path(N )| may all be calculated from the Large Node whose value is I N + distance(N ) as described above. If N is a Large Node, it has 2*32 more bits. If |path(N )| can be coded on 10 bits (i.e. its value is strictly less than 1024), then the next 4 bytes are coded according to scheme C1: the first bit is flagged, the next 21, the first 5 bits of D and the 2 free bits of the leaf whose value is head(N ) are used to code the suffix link of N . If |path(N )| ≥ 1024, then the next 4 bytes are coded according to scheme C2. The 27 last bits code for |path(N )|. The suffix link of N is then coded in the rightmost child (coding of B) whose field "right sibling" is zero. Finally, the last 27 bits of D code for head(N ).

Coding for the factor tree construction algorithm

Let us examine now how we must change the illi coding in order to use it in the implementation of our factor tree construction algorithm. As observed previously, the values head(F ) and |path(F )| of a leaf F can be deduced directly from the index of the leaf: the leaf F whose index is i is such that head(F ) = i and |path(F )| = |s|i. This is not true anymore in the case of a k-deep factor tree. Indeed, since some leaves are cut, a shift is introduced in the order in which a leaf is created and then inserted in the table for the leaves. We can clearly identify the moment when a leaf is cut and a shift is thus introduced. This happens at line 11 of the algorithm given in Figure 5. An easy way out would be at each such point to create and insert in the table a dummy leaf as we could then again deduce the values of head(F ) and |path(F )| from the index of F . This solution is however not satisfying because memory space is unecessarily lost and, furthermore, we cannot produce the list of all the occurrences associated with a leaf. Another way of solving the problem consists in introducing a coding of the occurrences of a leaf in the form of a linked list. At line 11 in the algorithm, if a leaf F is reached at step p, a new cell is created in the table for all the leaves whose index in the table is pk. We then store in the cell the index of F . In the tree, the link to F (field first child of the father or sibling of the left brother) is replaced by a link to the leaf whose index is pk.

This new procedure presents two problems:

• when one traverses a list of occurrences, an additional bit is required to indicate that we have reached the end of the list, but, as we have seen above, all the bits of the field have already been used;

• to obtain the information "right sibling/suffix link of the father", we need to examine all the occurrences of the leaf, which implies that the complexity of the construction algorithm is no longer in O(|s|).

In order to address these problems, the coding of a node has to be modified. In particular, we need to "free" bits in the coding scheme of a leaf. We thus modify the coding of the nodes in the following way. The suffix link of a node is still either to a node which exists already, or to the next node which will be created just after. In the case where the suffix link is to the next node, we have a Small Node and the index of the suffix link is not coded but is deduced from the node. In the other case, we have a Large Node. Let us denote by i the index of N in the table of the nodes. If i ≤ 2 26 , we know that the suffix link can be coded using 26 bits and therefore, we employ the same coding as above without using the 2 bits of the leaf whose index is head(N ). If i > 2 26 , we use the coding scheme C1 below. If |path(N )| can be coded on 8 bits (i.e., its index is less than 256), then the 23 bits of C1 plus the 5 bits of D are used to code the suffix link. If |path(N )| ≥ 256, we follow the coding scheme C2 and the suffix link is found in the rightmost child.

C1

↓ 23 suffixlink bits 8 -path(N)-bits

We thus have 32 bits per leaf and not 30 anymore. We recall that the index of a leaf requires 27 bits. We also need 1 bit to indicate whether we have reached the end of a linked list. In the case where we are at the end of a list, we remain with 31 bits, 29 to code the value right sibling/suffix link and 1 to indicate whether the index of the right sibling is nil. If we have not reached the end of a list, then of the 31 remaining bits, 27 are used to code the position of the next occurrence. To guarantee that we can obtain the value right sibling/suffix link in constant time, we use the last 4 bits to code part of the index of the last cell. In this way, in the worst case, we need to traverse the first 7 cells of the list before being able to jump directly to the last cell. To improve access time to the last cell, we optimise the code in the following way: if we are in cell c of the list, then we have already read c * 4 bits of the index of the last cell. If i is smaller than 2 c * 4 , then the value read is the index of the last cell (because this index is less than c). Another possible optimisation that has not yet been implemented consists in using in cell c, with c coded on j bits, 32 -1j bits to code part of the index of the last cell. Indeed, the cell after i has a smaller index and thus can be coded on j bits. In what is shown below, B1 represents the model used for the last cell, otherwise it is the model B2 that is employed.

B1 1 ↓ 29 suffixlink/branchbrother bits B2 0 4 27 next leaf bits
The algorithm used to insert a cell in the linked list is the following. Denoting by j the position of the next occurrence (last considered cell in the table for the leaves), by i the index of the leaf to which an occurrence is added and by e the index of the leaf at the end of the list whose first cell is i, we do the following:

• while looking for e, we:

check whether the value e has already been coded in the first cells of the list; -determine the index l of the last cell reached before e. • if e has already been coded, we insert cell j after cell l and i stays at the head of the list;

• otherwise, we place j at the head of the list. Its coding follows model B2. We then need to update the pointers to i in the tree so that they point to j.

An example of the procedure for inserting a cell is given in Figure 8.

Experimental results

Suffix and factor tree construction time and space occupancy

Our first test uses 43 files from the Canterbury Corpus [START_REF] Arnold | A Corpus for the Evaluation of Lossless Compression Algorithms[END_REF] and the Calgary Corpus [START_REF] Bell | Text Compression[END_REF]. All tests have been done on a PC with a single 1GHz processor with 4Go of RAM memory under linux Debian/Gnu. Whenever possible, we added a termination symbol at the end of the file. The table presented below contains the following information (in order):

• the name of the file with, in parenthesis, its type: t for a text file, b for a binary file, d for DNA and f for a file in formal language;

• the length of the text;

• the size of the alphabet used in the file;

• the results obtained with a suffix tree using the illi coding:

execution time in seconds;

space occupied in bytes;

• the results obtained with a k-deep factor tree using our coding and for k = 20 then k = 10:

execution time in seconds;

the memory gain (in %) in relation to a suffix tree with the illi coding;

• the results obtained with the k-deep factor tree with our coding for a memory gain of at least 15%:

execution time in seconds;

value of k.

The last line indicates the total size of the data, followed by the average value (time, space or gain) by column. In the case where there are 2 values in a cell, the second value corresponds to the average of the values in the column except for the files aaa and alphabet.

Let us start by commenting the space memory used by both data structures. We may observe first that the type of results obtained depends on the size of the file. Indeed, cutting the tree at a depth of 20 when the text is short (for instance, paper5 which makes 11Kb) produces a weaker space gain than cutting it also at a depth of 20 when the text is long (for instance, world192 which makes 2,5Mb). However, independently from the type and size of the file, the factor tree offers an often significant gain for k = 10 as well as for k = 20, except for the files random and kennedy. The text in these two files present the same characteristic: they are not structured and do not contain long repeats.

The files containing a text written in a formal language are the most structured ones and are among the ones yielding the best results. For example, a file such as cp which is in html format contains long repeats that are specific of the language (e.g. the sentence <a href="http://www. with 20 characters). The structure itself of formal texts favours the existence of deep nodes in the tree and therefore a reasonable cut (10 ≤ k ≤ 20) leads to very good memory gains such as 25.98% for k = 10. The files aaa and alphabet are equally favourable to both a suffix tree with the illi coding and a k-factor tree with our coding in the sense that they too contain long repeats. In fact, files such as these two represent the best cases for both approaches. They lead to the best gains for the factor tree relatively to a suffix tree.

Text files produce also good memory gains. However, natural languages do not in general contain very long repeats and the gain is thus in general less strong, although there may be exceptions to this. For instance, the bible file where sentences like " And God ..." favour the presence of nodes at a depth of more than 10. The average gain of 18.28% for a height k = 10 indicates that the factor tree is well adapted to this type of file.

The results on binary files are less easy to predict. Indeed, the file pic, which codes for an image, contains long repeats due to the repetitition of identical lines and the gain obtained on it is good.

For the other files, the results are disappointing. There are two reasons for this: the alphabet of these files is often big and since the text in the files are not structured, long repeats are rare. These files present therefore some of the less good results with, nevertheless, an average gain of 14.25% for k = 10. Let us now examine the results obtained on biological data, in this case, DNA sequences. The sequences considered were chromosomes 14 and 22 of Homo sapiens (retrieved from the database of the NCBI [21] and denoted by C14 and C22), and seven sequences retrieved from the EMBL database (the first column indicates their primary access number). The results on chromosomes 14 and 22 of man are encouraging given the size of the tree in memory (more than 1Go), the 15% gain of the factor tree over the suffix tree represents a real gain. Otherwise, although the gain remains important for k = 10, results become disappointing for k = 20.

Figure 9 shows the results for different values of k on the sequence with EMBL primary access number AE000111 which corresponds to the sequence covering the first 400 entries of the complete genome of Escherichia coli in the EMBL database. We see that, as expected [START_REF] Apostolico | Self-Alignement in Words and Their Applications[END_REF] [23], log 4 |s| is a good indicator of the value of k starting from which the gain diminishes as this value is increased. The curve, that presents the same behaviour with random sequences (results not shown), thus confirms that the tree is almost complete up to a depth of log |Σ| |s|. More details may be found in [START_REF] Apostolico | Self-Alignement in Words and Their Applications[END_REF] and [START_REF] Szpankowski | A Generalized Suffix Tree and Its (Un)expected Asymptotic Behaviors[END_REF], where the authors study the internal repeats of a text and average height of a suffix tree. Observe that for DNA, the value of log 4 |s| goes from 10 for a sequence of 1Mo to 13 for a sequence of 100Mo. However, one must remember that the nature of these sequences may change these results.

Finally, let us consider the construction time required by both structures. In the case of the factor tree, we can see that the tests added by our algorithm during construction lead to a slight increase in the execution time. However, as soon as values of k between 10 and 20 are reached, the factor tree is at least as performing as the suffix tree.

Execution time for pattern matching using a suffix or factor tree

We now present the results concerning the time required to do pattern matching with a suffix tree or a factor tree. More precisely, since the time for simply searching for a pattern (that is, just telling whether a motif is in a text) is the same for both trees, we rather examine the time taken in each case to enumerate all the positions of a pattern in the text. This is expected to be different because factor trees are cut at a depth k and a leaf points now to a list of occurrences instead of a single one as in the case of a suffix tree. We implemented for this a procedure that searches for a pattern and then realises a depth-first traversal of the tree (suffix or factor) until all the positions of the pattern are reached. This traversal is done in an iterative fashion using in both cases a static stack. At each position of pattern x in s, a function is called that does nothing. Since a single search plus enumeration takes a time that is too small to be measured, for each pattern sought, we repeated the same procedure until we obtained an overall time of the order of a tenth of a second. We did this operation for 1000 patterns randomly taken among the factors of s (the same for the suffix and the factor trees).

The table below shows the results obtained. The columns indicate the following (execution times are in microseconds):

• name of the file;

• size of the file;

• length of the pattern sought;

• results obtained with the suffix tree using the illi coding:

minimum execution time of the operation; -average execution time of the operation; -maximum execution time of the operation;

• results obtained with the factor tree using our coding: We see that the factor tree has search plus enumeration times that are equivalent and often better than those obtained using the suffix tree with the illi coding. It is interesting to observe that, in all cases, the maximal search time observed is greatly improved for a factor tree as against a suffix tree.

-

Conclusion

We introduced in this paper a useful structure for indexing the at most k-long factors of a string, and only those factors. The structure preserves the properties of a suffix tree, including the on-line characteristic of its construction, and can therefore replace it advantageously in some cases. We also showed that the modifications one must do to Ukkonen's construction in order to obtain a k-factor tree for a string s are easy.

Our experimental results show that this structure leads to often important gains in terms of the time for constructing the tree, memory space and time for some usages of the tree.

Figure 1 :

 1 Figure 1: Suffix trie of s = aabb (left), implicit suffix tree of s (center) and suffix tree of aabb$ (right).

Figure 3 :

 3 Figure 3: Ukkonen's algorithm: construction of the suffix tree for s; R is the root of the tree. The function length returns the size of the edge label between two nodes. The function AddString achieves the fast insertion.

Figure 4 :

 4 Figure 4: k-Factor tree construction algorithm. The horizontal lines indicate the substrings of s which are inserted into the tree during phase i. On the left, the substrings inserted for i = k -1 are shown and, on the right, the substrings of length at most k inserted for i = (for ≥ k).

4 .

 4 set lastLeaf to the leaf at the end of queue leaf 5.

else 6 .

 6 add s i from last position reached during the last insertion 7.if a leaf is created 8.add this leaf at the end of queue leaf 9.set lastLeaf to this leaf 10.

else 11 .

 11 set lastLeaf to the leaf reached 12.do 13.f orward ← length(F ather(lastLeaf ), lastLeaf) -1 14.

  28.set lastLeaf to this leaf 29.add this leaf at the end of queue leaf 30.if a node was not created in the call to AddString 31. endP hase ← true 32.

Figure 5 :

 5 Figure 5: Second part of the algorithm for the construction of the at most k-deep factor tree of a string s.

Figure 6 :

 6 Figure6: The suffix tree of s = ABAAB$, the right tree shows the suffix tree as it is coded by illi.

Figure 7 :

 7 Figure 7: An example of a best case for the illi coding, s = AAAA$. In the boxes, what the data that are really coded.

Figure 8 :

 8 Figure 8: Insertion in a list of occurrences. (a) The list contains only one cell, 19. (b) Insertion of occurrence 25, i = e = 19. (c) Insertion of occurrence 34 i = 25, e = 19 and l = 25.(d) Insertion of occurrence 40 i = 34, e = 19, l = 25, 19 is already coded in the cells 34 and 25, 40 is added after 25.

Figure 9 :

 9 Figure9: Results obtained with the factor tree on the sequence with EMBL primary access number AE000111. The Y -axis indicates the space occupied by the factor tree in bytes per input char and the execution time in seconds, the X-axis plots the values at which the tree is cut. The log curve represents log 4 |s|.

  a child to node with edge label start equal to end 12. e ←the label of the edge between node and child 13. if e end-start+1 not equal to s end Add to R a leaf L with edge label s 1 2. lastLeaf ← L 3. For i from 2 to |s|

	AddString(node,s,start,end)
	1. endJump ← f alse 2. while(not endJump) and ((end -start) not equal to 0) do 3. set child to the child of node that start with the letter s start
	4. 5. 6. 7.	if (end -start) is greater or equal to length(node, child) start ← start + length(node, child) node ← child else
	8. 9. done	endJump ← true
	10. if (end -start) is equal to 0 and node has not a child for letter s end 11.
	14. 15.	split e at position end -start add a leaf with start position equal to end to the new node
	16. done.
	Suffix Tree(s)
	1. 4. 5.	endP hase ← f alse do
	6.

add

  value of k; -minimum execution time of the operation; -average execution time of the operation; -maximum execution time of the operation;

	file	length pattern		suffix tree				factor tree
			length min	mean	max	k min	mean	max
	bible(t)	4047393	10 2.30	14.90	368.34	17 3.01	12.28	183.40
	bible(t)	4047393	10 2.30	14.90	368.34	10 2.03	7.80	13.75
	bible(t)	4047393	15 2.53	8.29	134.81	17 3.50	8.79	17.54
	bible(t)	4047393	15 2.53	8.29	134.81	15 1.99	8.66	15.95
	world192(t) 2473401	15 1.81	10.72	77.03	20 1.28	8.71	39.07
	world192(t) 2473401	25 1.97	8.90	70.02	25	0.0	8.59	18.69
	cp(f)	24604	10 0.84	5.50	19.27	18 0.85	5.79	17.08
	cp(f)	24604	10 0.84	5.50	19.27	12 0.99	5.08	13.43
	trans(f)	93696	20 0.92	5.28	45.79	59 0.46	6.12	26.92
	trans(f)	93696	40 1.05	5.28	39.33	40 1.36	6.01	11.82
	pic(b)	513217	60	0.0 8423.35 23333.33 204	0.0	4782.99	12999.99
	U00096	4639221	10 2.06	3.44	17.55	12 1.84	3.21	4.80
	U00096	4639221	12 2.16	3.22	12.68	12 1.97	3.13	4.93

Acknowledgment

We would like to thank Maxime Crochemore and Mathieu Raffinot for their help and for interesting discussions.


Marie-Pierre Béal

Sylvain Lombardy

Dominique Perrin

Embeddings of automata

We prove that any local automaton is contained in a complete one. The proof uses Nasu's masking lemma. We use the same technique to give a new proof that any weakly deterministic irreducible automaton is contained in a complete one.

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. We use the notation p • a = q to

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 problem of embedding an automaton into a complete one for several families of automata including local and weakly deterministic automata.

The problem of embedding 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 rational 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 1 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. 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 according to which any locally parsable rational code is included in a maximal one [START_REF] Bruyère | On maximal codes with bounded synchronization delay[END_REF], see also [START_REF] Berstel | Codes and Automata[END_REF].

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]. This result deals with the embedding of a shift of finite type into another one. Given a graph G, the edge shift on G is the set X G of biinfinite paths in G. The result states that if X G can be embedded in X H , then there is a graph K such that X K is isomorphic to X H and G is contained in K. We use this result in the particular case where X H is the full shift but the same proof can be used to obtain a more general result with an arbitrary subshift instead of the full shift.

We also use Nasu's masking lemma to give a new proof of a result of [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF] concerning weakly deterministic automata, which are such that the knowledge of the starting state and of a prefix of length d of the label of a path determines its first edge. These automata are also called right-closing in symbolic dynamics. We give a new proof using Nasu's lemma that any d-weakly deterministic automaton is contained in a complete one. This result can be reformulated in terms of codes. The basis of the stabilizer of a state in a weakly deterministic automaton is, by definition, a weakly prefix code (also called codes with finite deciphering delay).

We have written this paper in a self-contained form and in particular we adapt the proof of Nasu's lemma to our notation. express the fact that there is an edge p a → q in a deterministic automaton. It can be shown that an irreducible deterministic automaton is complete if and only if for each state p and letter a there is exactly 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)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 S-edge 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]). 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 1 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 2 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.
Proposition 3 Two strongly equivalent essential automata are equivalent.

Proof Let A = (P, E) and B = (Q, F ) be (R, S)-elementary equivalent automata on the alphabet

A. Let w = a 1 . . . a n ∈ L(A). Since A is essential, there is a path p -1 a0 → p 0 a1 → p 1 a2 → • • • p n-1 an → p n an+1 → p n+1 ,
with a 0 , a n+1 ∈ A. For each i = 0, . . . , n + 1, we have a i = r i s i with r i ∈ R pi-1qi and s i ∈ S qipi , and thus a path

p -1 r0 → q 0 s0 → p 0 r1 → q 1 s1 → p 1 • • • p n-1 rn → q n sn → p n rn+1 → q n+1 sn+1 → p n+1
using alternately entries of R and S. Then either r 0 = a 0 , . . . , r n+1 = a n+1 and

s 0 = • • • = s n+1 = 1 or r 0 = • • • = r n+1 = 1 and s 0 = a 0 , . . . , s n+1 = a n+1 .
We consider the first case, the other one being symmetrical. Since SR is the transition matrix of B, we have in B a path

q 0 a1 → q 1 a2 → • • • an → q n an+1 → q n+1 .
This shows that wa n+1 ∈ L(B) and thus w ∈ L(B).

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 . 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 3.

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 4 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). (resp. B i ) of Figure 3, we have

A 1 = (P 1 , E 1 ) with P 1 = {2, 3} and A 2 = (P 2 , E 2 ) with P 2 = {1} are rep- resented with continuous edges. We have B 1 = (Q 1 , F 1 ) with Q 1 = {2, 3, 4} and B 2 = (Q 2 , F 2 ) with Q 1 = {1, c, d}.
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   .
The following result will be used in Section 4.

B 1 ∩ A 1 B 2 ∩ A 2 B 3 ∩ A 3 Proposition 5 Let A 1 , A 2 , A 3 , B 3 be essential automata such that A 1 is an input merge of A 2 , A 3 is an output merge of A 2 and A 3 is a subautomaton of B 3 . Let B 2 be the Nasu extension of A 2 with respect to A 3 , B 3 . Then A 1 is a subautomaton of the maximal input merge B 1 of B 2 .
Proof Set A i = (P i , E i ) for i = 1, 2, 3 and let B i = (Q i , F i ) for i = 2, 3. Let M i be the transition matrix of A i for i = 1, 2, 3. Set M 2 = SR, M 3 = RS and let R, S be the matrices corresponding to the Nasu extension of A 2 . We have

Q 2 = P 2 ∪ (F 3 \ E 3 ) and for q 2 ∈ Q 2 , q 3 ∈ Q 3 , S q2,q3 = S q2,q3 ∪ {l(q 2 ) | q 2 ∈ F 3 \ E 3 , e(q 2 ) = q 3 } and R q3,q2 =    R q2,q3 if q 2 ∈ P 2 , q 3 ∈ P 3 1 if q 2 ∈ F 3 \ E 3 and o(q 2 ) = q 3 0 otherwise
Let p 2 , p ′ 2 ∈ P 2 be two states of A 2 that have the same output. Let us show that they also have the same output in B 2 . For this, suppose that (p 2 , a, r) is an edge of B 2 with r ∈ F 3 \ E 3 . Since the transition matrix of B 2 is S R, there is a state q ∈ Q 3 such that a ∈ S p2q and R qr = 1. It follows from the definition of S that q is in P 3 (indeed if q ∈ Q 3 \ P 3 , then p 2 ∈ F 3 \ E 3 , a contradiction). Since A 3 is obtained from A 2 by an output merge, there is a p ∈ P 2 such that R q,p = 1 and thus an edge (p 2 , a, q) in E 2 . Since p 2 , p ′ 2 have the same input in A 2 , we have also an edge (p ′ 2 , a, q) in E 2 . Thus there is an edge (p ′ 2 , a, r) in F 2 , which proves the assertion.

This shows that the automaton B 1 obtained from B 2 by merging the states with the same output, has A 1 as a subautomaton.

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.

As a particular case of a local automaton, an edge automaton is such that all edges have distinct labels. An edge automaton is both (0, 1) and (1, 0)-local.

A word w is said to be a constant for an automaton A if for p, p ′ , q, q ′ ∈ P such that p w → q and p ′ w → q ′ one has also p w → q ′ and p ′ w → q. The empty word is a constant only when the automaton has a single state.

Observe that when the automaton is deterministic, a constant is a word w such that the set Im(w) = {q ∈ P | p w → q for some p ∈ P } has at most one element.

Note that if A is an irreducible, complete, deterministic local automaton with more than one state, then a∈A

Im(a) = ∅, (1)
where Im(a) = {p•a | p ∈ P } (this property appears in [START_REF] Montalbano | Local automata and completion[END_REF]). Indeed, suppose that q ∈ a∈A Im(a). Let w be a word of maximal length which is not a constant.

Then for each letter a ∈ A, the word aw is a constant and thus Im(aw) has only one element. Thus for any state p we have p • w = q • w. Indeed, since A is essential, there is a letter a such that p ∈ Im(a). Then p, q ∈ Im(a), which implies p • w = q • w. This contradicts the fact that w is not a constant. 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.

Proposition 6 An irreducible automaton is local if and only if it is unambiguous and there exists an integer n such that any word of length n is a constant. Proof Suppose first that A is (λ, ρ)-local. Let c, c ′ be two paths from p to q labelled w. Since A is irreducible, there exist states r, s and paths r u → p, q v → s with |u| = λ and |v| = ρ. Since A is (λ, ρ)-local, the paths c, c ′ coincide. Thus A is unambiguous. Suppose next that p w → q and p ′ w → q ′ with |w| = λ + ρ. Let w = uv with |u| = λ and |v| = ρ. Let r, r ′ be such that

p u → r v → q and p ′ u → r ′ v → q ′ . Since A is (λ, ρ)-local, we have r = r ′ .
This implies that we also have paths p w → q ′ and p ′ w → q. Thus the condition of the statement is true with n = λ + ρ.

Conversely, let us assume that any word of length n is a constant and that

A is unambiguous. Let us show that A is (n, n)-local. Suppose that p u → q v → r and p ′ u → q ′ v → r ′ with |u| = |v| = n.
Then, since u and v are constants, we also have p u → q ′ v → r. Since A is unambiguous, this forces q = q ′ , whence the conclusion.

The least integer n such that any word of length n is a constant is called the order of the automaton. Note that a (λ, ρ)-local automaton has order at most λ + ρ. It 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 v when v is nonempty. It is clear that this automaton is (λ, ρ)-local.

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

Lemma 1 Let n be a nonnegative integer such that λ, ρ ≤ n, the free (λ, ρ)-local automaton has order n.

Proof 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) The following result shows that any (λ, ρ)-local automaton is strongly equivalent to a subautomaton of the free (λ, ρ)-local automaton.

w → (x, y ′ ) and (u ′ , v) w → (x, y) in F (λ,ρ) .
Proposition 7 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 ∈ Q 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 2 Any local unambiguous (local irreducible) automaton is a subautomaton of a complete (local irreducible) one with the same order.

The proof uses Nasu embeddings.

Proposition 8 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 , then the Nasu embedding of A 2 with respect to A 1 and B 1 , is a local automaton with the same order as B 1 .

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 1. 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 .

Proof of Theorem 2. Let A be a local unambiguous automaton of order n. Without loss of generality, one can assume that A is (λ, ρ)-local with λ, ρ ≤ n (for instance one can choose λ = ρ = n). By Proposition 7 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 1, the free (λ, ρ)-local automaton has order n. Since A λ+ρ is included in the complete (λ, ρ)-local automaton, we may build using repeatedly Proposition 8 a sequence B λ+ρ , . . . , B 1 , B 0 of complete unambiguous local 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. It is clear that if A is irreducible, then B is irreducible.
Example 6 Let A = A 0 be the deterministic automaton represented on the left of Figure 6. It is (3, 0)-local and has order 3. Indeed, the action of a, b on the set of states represented on the right of Figure 6 shows that any word of length 3 has an image of cardinality at most 1. Note that A cannot be completed in a local deterministic automaton. Indeed, we have 2 ∈ Im(a) ∩ Im(b) contrary to [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF]. We have represented on Figure 7 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 Figure 7. The matrices R, S such that the transition matrix of A 1 is RS and the transition matrix of A is SR are

R =     1 0 0 0 1 0 0 0 1 0 1 0     , S =   0 a 0 b 0 0 b 0 a 0 0 0   .
The auxiliary graph is shown on Figure 8. The final result is shown on Figure 9. It is a complete local automaton containing A.

To check that it is complete, one can apply the subset construction to build an equivalent deterministic automaton. Since A is irreducible and local, this construction may be started from any state. Then we can check that each state has outgoing edges carrying each letter.

Weakly deterministic automata

An automaton A is said to have delay d if for any pair of paths

p a → q z → r, p a → q ′ z → r ′ ,
with a ∈ A, z ∈ A * and |z| = d then q = q ′ . We say that the automaton is weakly deterministic if it has delay d for some integer d ≥ 0. The minimal delay of an automaton A is the least integer d such that A has delay d.

Weakly deterministic automata are also known in symbolic dynamics as right-closing automata.

Thus a deterministic automaton has delay 0. Observe that if A has delay d, then for any word w, and for any pair of paths

p w → q z → r, p w → q ′ z → r ′ ,
with w, z ∈ A * and |z| = d, the paths p w → q and p w → q ′ are equal.

Proposition 9 Let A be an essential automaton. If A is local, it is weakly deterministic. If it is weakly deterministic, it is unambiguous.

Proof Suppose first that A is (λ, ρ)-local. Let p a → q z → r and p a → q ′ z → r ′ be paths with |z| = ρ. Since A is essential, there exists a path s y → p with |ya| ≥ λ. Since we have paths s ya → q z → r and s ya → q ′ z → r ′ , we have q = q ′ . Thus A has delay ρ.

Suppose next that A is has delay d. Two paths from p to q with the same label may be extended to the right arbitrarily. This forces them to coincide. Thus A is unambiguous.

We will use the following result.

Proposition 10 Let A 1 and A 2 be (R, S)-strongly equivalent irreducible automata. If the automata A 1 is weakly deterministic, then A 2 also, and their minimal delays differ at most by one.

Proof Let us suppose that A 2 has delay d -1 and show that A 1 has delay d. We treat the case where the entries of R are in P(A) and the entries of S are in {0, 1}. The other case is similar.

Let

p 0 a0 → p 1 a1 → • • • p d → p d+1 and p 0 a0 → p ′ 1 a1 → • • • a d
→ p ′ d+1 be two paths in A 1 of length d + 1 with the same origin and the same label a 0 a 1 • • • a d , with a i ∈ A. Since A 1 is irreducible, there exists an S-edge q 0 → p 0 . Thus we have, in the auxiliary graph, paths q 0 → p 0

a0 → q 1 → p 1 a1 → q 2 • • • a d → p d+1 and q 0 → p 0 a0 → q ′ 1 → p ′ 1 a1 → q ′ 2 • • • a d → p ′ d+1 .
Since A 2 has delay (d -1), we have q 1 = q ′ 1 and q 2 = q ′ 2 . This implies p 1 = p ′ 1 . Thus A 1 has delay d.

The following statement shows that an input merge cannot increase the delay. → r and p a → q ′ u → r ′ be two paths in A 2 where a ∈ A and u ∈ A d . We then have paths p

a → q u → r and p a → q′ u → r ′ in A 1 .
Since A 1 has delay d, we have q = q′ . Since the inputs of q and q ′ are not disjoint, we have q = q ′ . Thus A 2 has delay d.

The following result, which already appears in [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF], is the analogue of Theorem 2 for weakly deterministic automata. The proof uses again Nasu embeddings.

Theorem 3 A weakly deterministic irreducible automaton is a subautomaton of a complete one with the same delay.

Observe that, contrary to Theorem 2, the above statement is trivial if the result is not required to be irreducible.

We first prove the following result which shows that a weakly deterministic irreducible automaton is strongly equivalent to a deterministic irreducible automaton.

Proposition 12 If A is a weakly deterministic irreducible automaton with delay d ≥ 1, there exist automata A 1 and A 2 such that A is an input merge of A 1 , A 2 is an output merge of A 1 and A 2 has delay d -1.

Proof Set A 0 = A and A i = (P i , E i ) for i = 0, 1, 2. Let P 1 = E 0 and let E 1 be the set of triples (e, a, f ) with e, f ∈ E 0 and a ∈ A such that e, f are consecutive edges of A and a is the label of f . In this way, there is an input merge from A 1 to A 0 obtained by merging the states with the same third component. The full statement of the result of [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF] is more general and Theorem 3 and its proof can be extended as follows. Let A be an irreducible edge automaton. Any weakly deterministic irreducible automaton B such that L(B) ⊆ L(A) is a subautomaton of a weakly deterministic irreducible automaton C which is equivalent to A and has the same delay.

We have not been able to found a way to prove by Nasu extensions the analogous result of [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF]

Example 1 Figure 1 :

 11 Figure 1: Two elementary equivalent automata A (on the left) and B (on the right). The transition matrices M and N of A and B are M = [a + b] , N = a b a b .

1 Figure 2 :

 12 Figure 2: The auxiliary graph (with continuous edges).

Example 3 Figure 3 :

 33 Figure 3: The Nasu embedding B 2 of A 2 with respect to A 1 , B 1 . The automataA 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 have B 1 = (Q 1 , F 1 ) with Q 1 = {2, 3, 4} and B 2 = (Q 2 , F 2 ) with Q 1 = {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.

  Figure 3: The Nasu embedding B 2 of A 2 with respect to A 1 , B 1 . The automataA 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 have B 1 = (Q 1 , F 1 ) with Q 1 = {2, 3, 4} and B 2 = (Q 2 , F 2 ) with Q 1 = {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.

Example 4 Figure 4 :

 44 Figure 4: A (1, 1)-local automaton.

Example 5 Figure 5 :

 55 Figure 5: The free (1, 1)-local automaton. It has order 1.

Figure 6 :

 6 Figure 6: A local automaton A and the action on subsets.

Figure 7 :

 7 Figure 7: A split A 1 of A and its completion B 1 with the dotted edges.

Theorem 2 Figure 8 :Figure 9 :Example 7

 2897 Figure 8: The auxiliary graph (with continuous edges). The automata A and A 1 are represented with dashed edges and the additional edges with dotted lines.

Figure 10 :

 10 Figure 10: The local automata B, C on the left (with the additional dotted edge for C), and A on the right.

Figure 12 :

 12 Figure12: Let A = A 0 be the automaton with delay 1 represented on the left with continuous lines. The automaton A 1 is represented at the center. The automaton A 2 obtained by merging states 1a1 and 1a2 is shown on the right. It is deterministic and can be completed by adding an edge e labelled b from state 2 to state 1 represented with dashes (another solution would be to add a loop labelled b on 2). Working backwards, the Nasu embeddings of A 1 and A 0 appear with dashes. The result on the left is a complete automaton B 0 with delay 1 containing A 0 as a subautomaton.

Figure 13 :

 13 Figure 13: Another embedding of the previous automaton.

  Proposition 11 Let A 1 be an input merge of A 2 . Then A 1 and A 2 have the same minimal delay.Proof The delay of a (input or output) merge cannot be larger than the original one. Hence if A 2 has delay d, then A 1 has delay d. Conversely, suppose that A 1 has delay d. Let p

a → q u

  concerning bi-closing automata, i.e. which have finite delay in both directions.

	Index
	automata
	elementary equivalent , 3
	equivalent, 5
	strongly equivalent, 5
	automaton
	bi-closing, 18
	complete, 2
	delay, 14
	essential, 2
	irreducible, 2
	local, 8
	minimal delay, 14
	order, 9
	right-closing, 15
	unambiguous, 2
	weakly deterministic, 14
	auxiliary graph, 3
	bipartite code, 3
	code
	locally parsable, 2
	weakly prefix, 2
	constant, 9

de Bruijn automaton, 10 deciphering delay, 2 delay, 14 edge automaton, 9 elementary equivalent automata, 3 equivalent automata, 5 free local automaton, 10 input, 3 input merge equivalence, 4 input split, 4 locally parsable, 2 minimal delay, 14 Nasu embedding, 6 order, 9 output, 3 output merge equivalence, 4 output split, 4 subautomaton, 2 synchronization delay, 2 weakly deterministic automaton, 14 weakly prefix, 2

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

Let A 2 be the automaton obtained from A 1 by merging the states having the same input. By Proposition 11 and since A 0 has delay d, A 1 has delay d. Let us verify that A 2 has delay d -1. Consider two paths α

. These paths are the image under the output merge of two paths in A 1 of the form (i, b, p) → s in A. Since A has delay d, this forces p = p ′ . But since (p, a, q) and (p, a, q ′ ) have the same input in A 1 , they belong to the same class of the output merge equivalence giving A 2 . This forces The particular solution given in [START_REF] Ashley | Surjective extensions of sliding block codes[END_REF] is not the same as the one described above. Let us explain how it works on this example.

The embedding is based on the observation that an automaton with delay d is complete if and only if for each state p the following condition is satisfied: for each word u of length d such that there is a path labelled u starting at p, there also a path labelled ua starting at p for each a ∈ A.

Since state 2 can be followed by ba but not by bb, we add an edge labelled b from 2 to a new state called b and such that there is an edge labelled b going to state 1. Further, since state b can be followed by ba but not by bb, we add a loop labelled b on state b. The above condition is now satisfied for any state. Let B 0 be the complete automaton thus obtained.

This automaton is obtained by the previous construction starting with the completion of the deterministic automaton A 2 shown on the right and working


A Basis for Repeated Motifs in Pattern Discovery and Text Mining

Nadia Pisanti, Maxime Crochemore, Roberto Grossi, Marie-France Sagot

To cite this version:

Nadia Pisanti, Maxime Crochemore, Roberto Grossi, Marie-France Sagot. A Basis for Repeated Motifs in Pattern Discovery and Text Mining. 2002. hal-00627828