Maxime Crochemore

Costas S Iliopoulos

Maureen Korda

Maxime Crochemore Costas

S Iliopoulos

Two-dimensional Pre x String Matching and Covering on Square Matrices

published or not. The documents may come

Introduction

In recent studies of repetitive structures of strings, generalized notions of periods have been introduced. A typical regularity, the period u of a given string x, grasps the repetitiveness of x since x is a pre x of a string constructed by concatenations of u. A substring w of x is called a cover of x if x can be constructed by concatenations and superpositions of w. A substring w of x is called a seed of x if there exists a superstring of x which is constructed by concatenations and superpositions of w. For example, abc is a period of abcabcabca, abca is a cover of abcabcaabca, and abca is a seed of abcabcaabc. The notions \cover" and \seed" are generalizations of periods in the sense that superpositions as well as concatenations are considered to de ne them, whereas only concatenations are considered for periods.

Given a string x of length n and a pattern p of length m, the pre x string matching problem is that of determining, for every position in x, the longest pre x of p that occurs in that position. Main and Lorentz introduced the notion of pre x string matching in ML84] and presented a linear time algorithm for it. In two dimensions, the pre x string matching problem is that of determining, for every position in a given n n text matrix T, the longest pre x of a given m m pattern matrix P that occurs in that position. The two-dimensional pre x string matching problem can be solved using the LSu x tree construction of Giancarlo (see G93], G95]). The LSu x tree for T, de ned over an alphabet , takes O(n 2 (log j j+log n)) time to build. Giancarlo's construction is the two-dimensional analog of the su x tree ( W]). Two-dimensional dictionary matching and two-dimensional pattern retrieval (see G95]) are among the applications of the Lsu x tree; one can use the Lsu x tree to derive O(n 2 (log j j + log n)) time for the two-dimensional pre x string matching problem. Here we present an optimal linear time algorithm for the two-dimensional pre x string matching problem that makes use of the notion of a two-dimensional failure function (also used in ABF92]) as well as the Aho-Corasick automaton ( AC95]) in order to reduce the number of substring comparisons to linear. Both constructions are dependent on the alphabet. In the case of xed alphabets, the algorithm presented here is faster than the one presented in G95] by a factor of O(logn) .

In computation of covers, two problems have been considered in the literature. The shortest-cover problem is that of computing the shortest cover of a given string of length n, and the all-covers problem is that of computing all the covers of a given string. Apostolico, Farach and Iliopoulos AFI91] introduced the notion of covers and gave a linear time algorithm for the shortest-cover problem. Breslauer Br92] presented a linear time on-line algorithm for the same problem. Moore and Smyth MS94] presented a linear time algorithm for the all-covers problem. In parallel computation, Breslauer 1 Br95] gave an optimal O( (n) log log n)-time algorithm for the shortest cover, where (n) is the inverse Ackermann function. Iliopoulos and Park IP94] gave an optimal O(log log n)-time (thus work-time optimal) algorithm for the shortest-cover problem.

Iliopoulos, Moore and Park IMP93] introduced the notion of seeds and gave an O(n log n)-time algorithm for computing all the seeds of a given string of length n. For the same problem Ben-Amram, Berkman, Iliopoulos and Park BBIP94] presented a parallel algorithm that requires O(log n) time and O(n log n) work. Apostolico and Ehrenfeucht AE93] considered yet another problem related to covers.

In this paper we generalize the all-covers problem to two-dimensions and we present an optimal linear time algorithm for the problem. Let P be a square submatrix of a square matrix T ; we say that P covers T (or equivalently P is a cover of T ), if every point of T is within an occurrence of P . The two-dimensional all-covers problem is as follows: given a two-dimensional square matrix T , compute all square submatrices P that cover T . While the algorithms for the shortest-cover problem AFI91,Br92,Br95,IP94] rely mostly on string properties, our algorithm for the two-dimensional all-covers problem is based on the Aho-Corasick Automaton and \gap" monitoring techniques.

A variant of the covering problem (see DS]) de ned above, was shown to have applications to DNA sequencing by hybridization using oligonucleotide probes: given string x, compute a minimal set of strings of xed length k that cover x; the strings of the minimal set are said to be the k-covers of x. The k-covering problem is closely related to the string pre x matching problem, dictionary matching problem and the Aho-Corasick Automata; techniques employed here as well as the ones used by Giancarlo in G95], could lead to e cient sequential and parallel solutions for the k-covering problem.

The paper is organized as follows: in the next section we present some de nitions and results used in the sequel. In section 3 we present a linear time algorithm for computing all the borders of a square matrix. In section 4 we present a linear time algorithm for computing the diagonal failure function of a square matrix (an algorithm similar to the one in ABF92]). In section 5 we present a linear time algorithm for the two-dimensional pre x string matching problem. And nally in section 6, we present a linear time algorithm for computing all the covers of square matrices.

Preliminaries

A string is a sequence (concatenation) of zero or more symbols from an alphabet . The set of all strings over the alphabet is denoted by . The string xy is a concatenation of two strings x and y. The concatenations of k copies of x is denoted by x k . A non-empty string x of length n is represented by x 1 x 2 x n , where x i 2 for 1 i n. A string w is a substring of x if x = uwv for u; v 2 ; we say that w occurs at position j of x if and only if x j x j+l 1 = w 1 :::w l , where l is the length of w. A string w is a pre x of x if x = wu for u 2 ; furthermore we de ne pre x k (x) = x 1 x 2 : : : x k . Similarly, w is a su x of x if x = uw for u 2 ; furthermore we de ne su x k (x) = x n x n 1 : : : x n k+1 . A pre x x 1 :::x p , for some 1 p < n of x is a period of x, if x i = x i+p for all 1 i n p. The period of a string x is the shortest period of x.

A two-dimensional string is an n 1 n 2 matrix drawn from . In this paper, we deal exclusively with the special case n = n 1 = n 2 , where the matrix is square. The n n square matrix T can be represented by T 1 n; 1 n]. An m m matrix P is a submatrix of T, if the upper left corner of P can be aligned with an element T i; j], 1 i; j n m + 1 and P 1 m; 1 m] = T i i + m 1; j j + m 1]. In this case, the submatrix P is said to occur at position i; j] of T. A submatrix P is said to be a pre x of T if P occurs at position 1; 1] of T. Similarly, a submatrix P is a su x of T if P occurs at position n m + 1; n m + 1] of T.

A string b is a border of x if b is a pre x and a su x of x. The empty string and x itself are trivial borders of x. An m m submatrix P is a border of T, if P occurs at positions 1; 1]; n m + 1; 1]; 1; n m + 1] and n m + 1; n m + 1] of T. The empty matrix and the matrix T itself are trivial borders of T. Fact 1. A string u is a period of x = ub if and only if b is a non-trivial border of x.

Proof . It follows immediately from the de nitions of period and border. Fact 2. A cover of string x is also its border. A cover of matrix T is also its border.

Proof . A cover of a string (matrix) occurs as both a pre x and a su x and therefore it is a border. The Aho-Corasick Automaton AC75] was designed to solve the multi-keyword pattern-matching problem: given a set of keywords fr 1 ; r 2 :::; r h g and an input string t of length n, determine for every keyword r i whether or not it occurs as a substring of t. The Aho-Corasick pattern matching automaton is a six-tuple (Q; ; g; h; q 0 ; F), where Q is a nite set of states, is a nite alphabet input, g : Q ! Q fail is the forward transition, f : Q ! Q is the failure function (link), q 0 is the initial state and F is the set of nal states (for details see AC75]).

Informally, the automaton can be represented as a rooted labelled tree augmented with the failure links. The label of the path from the root (initial state) to a state s is a pre x of one of the given keywords ; we denote such label by l s . If s is a nal state , then l s is a keyword. There are no two sibling edges which have the same label. The failure link of a node s points to a node f (s) such that the string l f (s) is the longest su x of l s that is a pre x of another keyword (see Figure 1 for an example.) The following theorem can be found in AC95]. In the sequel we shall need to perform string comparisons using the Aho-Corasick automaton and the following results by Harel and Tarjan HT84], Scheiber and Vishkin SV88] and Berkman and Vishkin BV94] will be used in guiding us within the automaton:

Theorem 2.2 Let T be a rooted tree with n nodes and let u; v be nodes of the tree. One can preprocess T in linear time, so that the following queries can be answered in constant time:

(i) Find the lowest common ancestor of u and v.

(ii) Find the k-th level ancestor node on the path from node u to the root where the rst ancestor of u is the parent of u. Using the above theorem one can derive the following two useful corollaries:

Corollary 2.3 Given the Aho-Corasick automaton for keywords r 1 ; r 2 ; ::::; r h and allowing linear time for preprocessing, the query of testing whether pre x k (r i ) = r m requires constant time.

Proof . We preprocess the automaton as required by the Berkman-Vishkin algorithm. We can identify the ancestor node, s, of the leaf r i , which corresponds to the k-th pre x of r i in constant time. This node is the (jr i j k)-th ancestor on the path from the leaf r i ( nal state) to the root (initial state). The equality holds only when s is also the leaf ( nal state) r m .

Corollary 2.4 Given the Aho-Corasick automaton for keywords r 1 ; r 2 ; ::::; r h and allowing linear time for preprocessing, the query of testing whether pre x k (r i;d ) = r m requires constant time, where r i;d = r i d::jr i j]. Proof . Let r i = 1 2 q and r i;d = d d+1 q . Then we have pre x k (r i;d ) = d d+1 d+k 1 . Let v be the d + k-th node on the path from the root to the leaf r i . Using the failure links it is possible to construct a path v; u 1 :::; u t ; r from the node v to the root r. It is not di cult to see that the label of the path from the root r to u j is s := d+k l d+k l+1 d+k , where l is the distance of u j from the root r (see Figure 2). One can see that pre x k (r i;d ) is a label of a path from the root to a node u, if and only if u is one of the u j 's. One can say that equality of the query holds if u j , for some j, is the leaf r m .

Given the automaton one can answer the query in constant time as follows.

Consider the following tree T : root is the initial state of the Aho-Corasick automaton, nodes are the nodes of the automaton and edges the failure links of the automaton. Let pre x k (r i;d ) be associated with a node v as above. It is not di cult to see that pre x k (r i;d ) = r m if and only if the Lowest Common Ancestor of r m and v in T is r ma condition that can be checked in constant time by the BV94] algorithm. By Fact 2, all borders of a string x or matrix T are candidates for covers. Our algorithm for the all-covers problem starts by computing all the borders of T and nds covers among the borders.

The algorithm is subdivided in the following three steps: 1. Compute all the borders B 1 ; B 2 ; B k of the matrix T and derive the candidates for covers. Here we use the fact that a cover of T is also a border. Let B k be the largest candidate border. 2. For every position i; j] of T , compute the longest pre x of B k that occurs at that position. We next \round down" these occurrences to the nearest border size, thus nding the largest border that occurs in that position. 3. We begin a gap monitoring program starting with B k . We consider all occurrences of B k in T and we check whether there are any positions of T that are not covered by an occurrence of B k {we call these positions \gaps" (see section 6 for a formal de nition). If there is a gap, then B k is not a cover. We proceed by considering whether B i 1 covers T for all i = k 1; :::; 1, again by monitoring their gaps.

Computing All Borders and Candidates

Here we describe a linear time algorithm for computing all the square borders of an n n matrix T . The algorithm makes use of two auxiliary n n matrices C and R, where C i; j] := 1 , if and only if the j-th column of T has a border of length i and R i; j ] := 1, if and only if the j -th row of T has a border of length i; otherwise C i; j ] = R i; j ] = 0. Formally C i; j ] = 1; T 1::i; j ] is a border of T 1::n; j ]; 0; otherwise. R i; j ] = 1; T j; 1::i] is a border of T j; 1::n]; 0; otherwise.

We compute all the borders of every row and column of T using the Knuth, Morris and Pratt ( KMP77]) algorithm. Furthermore we also use matrix M , such that:

M i] = 1; R i; j ] = C i; j ] = 1; 8 1 j i AND R i; l] = 1; 8 n i + 1 l n; 0; otherwise.

Lemma 3.1. The square submatrix T 1::i; 1::i] is a border of T if and only if M i] = 1. Proof . Assume that M i] = 1. From the de nition of M i] it follows that R i; j ] = 1; for all 1 j i, which in turn implies that rows r 1 ; r 2 ; :::; r i all have borders of length i. Therefore T 1::i; 1::i] occurs at position 1; n i + 1] of T . Similarly, from the fact that C i; j ] = 1; for all 1 j i the columns c 1 ; c 2 ; :::; c i all have borders of length i. Therefore T 1::i; 1::i] occurs at position n i + 1; 1] of T . From the fact that R i; j ] = 1; for all n i + 1 j n it follows that rows r n i+1 ; r n i+2 ; :::; r n all have borders of length i, which in turn implies that T 1::i; 1::i] occurs at position n i + 1; n i + 1] of T .

The converse follows similarly.

Based on this lemma, the following algorithm is proposed to compute the borders of T : begin Compute C i; j ], 1 i; j n ; Compute R i; j ], 1 i; j n ; comment Use the KMP algorithm. for 1 i n do if M i] = 1 then return T 1::i; 1::i] as a border of T ; comment It follows from Lemma 3.1. od end Algorithm 3.1 Theorem 3.2 Algorithm 3.1 computes all the borders of an n n matrix T in O(n 2 ) time.

Proof . The computation of the borders of each row and column takes O(n) time using the KMP algorithm, O(n 2 ) in total. Border veri cation of each diagonal candidate takes time O(i), O(n 2 ) in total.

Although here we make use of the borders as candidates for covers, one can obtain a (perhaps) smaller set of candidates by modifying the matrices C and R as follows:

C i; j] = 1; T 1::i; j] is a cover of T 1::n; j]; 0; otherwise. R i; j] = 1; T j; 1::i] is a cover of T j; 1::n]; 0; otherwise.

One can compute all the covers of every row and column of T using the MS94] algorithm. The veri cation of the above set of candidates can be similarly done in linear time. These candidates may lead to a more e cient algorithm (as they may be fewer than the borders) but it does not change the asymptotic complexity.

Computing the Diagonal Failure Function of a Square Matrix

An m m submatrix P is said to be a diagonal border of an n n matrix T, if P occurs at positions 1; 1] and n m + 1; n m + 1] of T. We de ne the diagonal failure function f(i), of T, for 1 i n to be equal to k, where T 1::k; 1::k] is the largest diagonal border of T 1::i; 1::i] ; if there is no such k, then f(i) = 0 (see Figure 3-(i)). Below we present a linear time procedure for computing the diagonal failure function; a similar algorithm was presented in ABF92] and ABF94].

The computation of the diagonal failure function shadows the computation of the failure function given in the Knuth-Morris-Pratt algorithm, with the exception that character comparisons are now substring comparisons. The algorithm makes use of the Aho-Corasick multi-word automaton to perform these comparisons in constant time. First we construct the Aho-Corasick multi-word automaton for the set of words r 1 ; r 2 ; :::; r n ; c 1 ; c 2 ; :::; c n , where r i = T i; i]T i; i 1] T i; 1]; 1 i n and c i = T i; i]T i 1; i] T 1; i]; 1 i n (see Figure 3-(ii)). Secondly, at iteration i, we have computed f(i) = k and we proceed to compute f(i+1) by comparing r k+1 and c k+1 with

(ii) i i r (i) P P [i,i] [i,i] c k k Figure 3
pre x k+1 (r i+1 ) and pre x k+1 (c i+1 ) respectively (Recall that pre x k (x) = x 1 x 2 x k and su x k (x) = x k x k+1 x n with jxj = n.) Clearly, if both match, then we have f (i + 1) = k + 1. Otherwise, as in KMP, we recursively (on k) compare r k+1 and c k+1 with pre x k+1 (r i+1 ) and pre x k+1 (c i+1 ), with k := f (k), until both strings match.

Formally, the algorithm is as follows: begin

r i T i; i]T i; i 1] T i; 1]; 1 i n; c i T i; i]T i 1; i] T 1; i]; 1 i n;
R fr 1 ; r 2 ; :::; r n g; C fc 1 ; c 2 ; :::; c n g;

Construct the Aho-Corasick automaton for R and C ; Preprocess the automaton for LCA queries; f (1) 0; k f (1); for i = 2 to n do while pre x k+1 (r i ) 6 = r k+1 or pre x k+1 (c i ) 6 = c k+1 do comment The condition is tested as in Corollary 2.3. Proof . The computation of the Aho-Corasick automaton and their preprocessing require O(n 2 ) time. The condition of the while loop can be computed in constant time as in Corollary 2.3.

Pre x String Matching in Two Dimensions

Let P (the \Pattern"), T (the \Text") be m m; and n n matrices respectively. The two-dimensional problem of pre x string matching is that of determining, for every position in the text matrix T, the longest pre x of P that occurs in that position.

The algorithm below shadows the Main-Lorentz ( ML84]) algorithm on the diagonals of the text matrix T (see Figure 4) with the exception that character comparisons are now substring comparisons. We use the Aho-Corasick automata to perform string comparisons in constant time. In order to simplify the exposition, we only compute the maximum pre x of the pattern occurring at points below the main diagonal of the text. The main diagonal is said to be the 1-diagonal, and the diagonal starting at position d; 1] is said to be the d-diagonal.

In Algorithm 5.1 below, we rst construct the Aho-Corasick multi-word automaton for the set of rows r 1 ; r 2 ; :::; r n and r 0 1 ; r 0 2 ; :::; r 0 m of T and P. We also construct the Aho-Corasick multi-word automaton for the set of columns c 1 ; c 2 ; :::; c n and c 0 1 ; c 0 2 ; :::; c 0 m of T and P. Starting from the top of each d-diagonal, and sliding downwards (on the d-diagonal), we iteratively compute the maximum pre x of P at each point of the ddiagonal as follows: at the end of the j-th iteration, we have computed the largest pre x of P that is a su x of T d::d + j 1; 1::j] for all 1; :::; j. Next, we attempt to augment that occurrence by extending it by a row and a column (in a manner similar to the L-character used by Giancarlo in G93] and G95]); this is only possible when the relevant row and column of the text match the corresponding ones of the pattern. If such an extension of the occurrence of the pre x of P is not possible, then we make use of the diagonal failure link, and next we attempt to extend the pre x pointed to by the link. Analytically, the pseudo-code for solving the pre x string matching problem is presented below. begin r i T i; n]T i; n 1] T i; 1]; 1 i n; c i T n; i]T n 1; i] T 1; i]; 1 i n; comment The strings r i ; c i are the rows and columns of the text T reversed. r 0 i P i; i]P i; i 1] P i; 1]; 1 i m; c 0 i P i; i]P i 1; i] P 1; i]; 1 i m; comment The strings r 0 i ; c 0 i are similar to the ones in Figure 3-(ii).

r i,d d-diagonal 1-diagonal [d,1] [d,i-d+1] [i,i-d+1] c i,d
Figure 4 R fr 1 ; r 2 ; :::; r n ; r 0 1 ; r 0 2 ; :::; r 0 m g; C fc 1 ; r 2 ; :::; c n ; c 0 1 ; c 0 2 ; :::; c 0 m g;

Computing the Gaps

In this section we focus on the covering problem: given a square matrix T compute all sub-matrices S that cover T. Recall that a sub-matrix S covers T if every position of T is within an occurrence of S. The linear time algorithm below is based on gap monitoring techniques.

The algorithm makes use of the fact that a cover of T is also a border. We rst compute all the borders of T, let B k be the largest one. Next we compute the largest pre x of B k that occurs at every position of T. We \round down" these occurrences to the nearest border size. Then we begin a gap monitoring program starting with B k . We consider all occurrences of B k in T and we check whether there are any positions that are not covered by an occurrence of B k { these \uncovered" positions are called gaps. If there is a gap, then B k is not a cover. We proceed by considering whether B k 1 covers T. Note that B k 1 occurs in all positions of B k , thus we have to \add" some positions to the occurrences of B k to obtain the set of occurrences of B k 1 in T. In fact every insertion of a new position may \reduce" previous gaps. Also due to the fact that we now consider a smaller border, B k 1 , some positions previously covered by B k may now be left \uncovered", and therefore the gap size between previous gaps may \increase". We monitor all these changes and if all gaps are closed then the border is a cover. Analytically the steps of the Gap Monitoring Algorithm are as follows: Algorithm 6.1

Step 1. Compute all the square b t b t borders B t , 1 t k, of the input matrix T; Let B k be the largest border and without loss of generality b t < b t+1 ; 1 t < k.

For 1 i n, let F(i) = ft : b t i < b t+1 g and let C(i) = ft : b t 1 < i b t g. The \ oor" F function will be used for rounding down the maximum border pre xes computed in the next step and the \ceiling" C function will be used for rounding up the gap length in step 5.

Step 2. For every position i; j] of T compute the length d(i; j) of the maximum pre x of B k that occurs in that position by using Algorithm 5.1. Let P i; j] = F(d(i; j)), i.e. the index of the largest border that occurs at position i; j] of T. Here we round down the occurrence (of the pre x of B k ) to the nearest border size, because only borders are candidates for covers (see Fact 2).

Step 3. Let D t denote the lexicographicaly ordered list of positions e; j] such that (i) P i; j] = t, (ii) i e < i + b t . The list D t contains all positions of T which belong to the rst column of an occurrence of B t (see shaded area of the j-column of T in Figure 5-(i)). Furthermore each position p; q] of T is associated with a range p; q; l; r] if and only if p; q] 2 D t ; 8 t : l t r, p; q] 6 2 D l 1 and p; q] 6 2 D r+1 (see Figure 5-(ii)). In other words, a position p; q] is associated with a range p; q; l; r], if and only if, the position p; q] is within the rst column of an occurrence of all of the following borders B l ; B l+1 ; :::; B r , but the position p; q] is not within the rst column of an occurrence of either B l 1 or B r+1 . Note that a position may be associated with more than one range, e.g., in Figure 5-(ii), assuming that < l 1, we have p; q; l; r] and p; q; ; ]. The computation of these ranges is described in detail in the next section 6.2.

B T (ii) (i) i t B r γ-1 l-1 T [p,q] [i,j] B B γ B α B t B l Figure 5
Step 4. Next we de ne the Left and Right functions that will allow constant time deletion and insertion in updating the list D t , which will be kept as a doubly linked list. We formally de ne Left( p; q; l; r]) := p; q 0 ; l 0 ; r 0 ] if and only if p; q 0 ] is the rst entry to the left of p; q] in the p-th row of T for which l 0 l r 0 , where p; q; l; r] and p; q 0 ; l 0 ; r 0 ] are the ranges associated with positions p; q] and p; q 0 ] respectively; otherwise Left( p; q; l; r]) := p; 1; ; ] (Note that p; 1; ; ] is not a "true" range, it is merely used here as an endpoint for the Left function).

We formally de ne Right( p; q; l; r]) := p; q 00 ; l 00 ; r 00 ] if and only if p; q 00 ] is the rst entry to the right of p; q] in the p-th row of T for which l 00 l r 00 , where p; q; l; r] and p; q 00 ; l 00 ; r 00 ] are the ranges associated with positions p; q] and p; q 00 ] respectively; otherwise Right( p; q; l; r]) := p; n; ; ] (Note that p; n; ; ] is not a "true" range, it is merely used here as an endpoint for the Right function).

Step 5. First we need the following de nitions. For each position p; q] in D t , we de ne gap t ( p; q]) = q 00 q, where p; q 00 ; l 00 ; r 00 ] = Right p; q; l; r]. Although, the function gap t provides us with information of the gaps within D t , we need to classify these gaps according to their length. Thus, for 1 s k, we de ne GAP(s) to be the list of all positions p; q] of D t whose gap t ( p; q]) satisfy b s 1 < gap t ( p; q]) b s or equivalently s := C(gap t ( p; q])):

We also de ne

GAP(t) := GAP(k) GAP(k 1) GAP (t)
The list GAP (t) contains the positions of B t occurrences, whose distance (gap) to the next B t occurrence is larger than b t .

In this step we will consider the borders from largest to smallest. Let B t be the current border. Assume that we have computed the list D i and its associated GAP(i) for all i t and we proceed to construct D t 1 and its associated GAP(i); i = k; k 1; :::; t; t 1 as follows:

We have to consider ranges that fall in one of the following three categories:

(i) The ranges of positions that are not members of D t but which are members of D t 1 . These are ranges of positions p; q] of T which are not within the rst column of an occurrence of B t , but which are within the rst column of an occurrence of B t 1 . These are ranges of the form p; q; l; t 1] (terminating with t 1). In order to create D t 1 , these ranges have to be added to the list D t ; their insertion will alter the list GAP, hence we also need to modify the list GAP(t) in order to obtain the list GAP(t 1). (ii) The ranges of positions that are members of D t but which are not members of D t 1 . These are ranges of positions p; q] of T which are within the rst column of an occurrence of B t but not within the rst column of an occurrence of B t 1 . These are ranges of the form p; q; t; r] (with t in the third position). In order to create D t 1 , these ranges have to be deleted from the list D t ; their deletion will alter the list GAP, hence we also need to modify GAP(t) in order to obtain the list GAP(t 1). (iii) The ranges of positions that are members of both D t and D t 1 . There is no need to consider these ranges, since they do not cause any change in gapsize.

First we consider all positions p; q] with range p; q; l; t 1]. Note that p; q] is in D t 1 , but p; q] is not in D t (see (i) above). We will obtain D t 1 by inserting each of these positions p; q] in D t and modify the associated GAP lists accordingly, by means of the following operations: 5.1 Let p; q 0 ; l 0 ; r 0 ] = Left p; q; l; t 1]. The insertion of p; q] in D t will narrow the gap at position p; q 0 ], (in other words gap t ( p; q 0 ]) 6 = gap t 1 ( p; q 0 ])), hence we delete p; q 0 ] from the list GAP(C(gap t ( p; q 0 ])). 5.2 The gap size at position p; q 0 ] is gap t 1 ( p; q 0 ]) = q q 0 , thus we add p; q 0 ] into GAP(C(q q 0 )). Note that we round up the gap sizes to the nearest border size { since only borders are candidates for covers.

5.3 Now we consider the gap size at p; q]. Let p; q 00 ; l 00 ; r 00 ] = Right p; q; l; t 1]. The position p; q 00 ] is the nearest position to the right of p; q] in D t 1 . Therefore gap t 1 ( p; q]) = q 00 q. Thus we add p; q] into GAP(C(q 00 q)).

Again we round up the gap size to the nearest border size.

Now we consider all positions p; q] with range p; q; t; r]. Note that p; q] belongs to D t but it is not in D t 1 (see (ii) above). We update the lists D and GAP as follows:

5.4 Delete p; q] from the GAP(C(gap t ( p; q])). This is done, because the position p; q] is not a member of D t 1 . 5.5 Let p; q 0 ; l 0 ; r 0 ] = Left p; q; t; r] and p; q 00 ; l 00 ; r 00 ] = Right p; q; t; r] The gap at p; q 0 ] (in D t 1 ) has became larger (than the gap in D t ) with the deletion of the position p; q]. The new gap is between positions p; q 0 ] and p; q 00 ], therefore we place (p; q 0 ) into GAP(C(q 00 q 0 )).

After all ranges have been processed (as needed in cases (i) and (ii) above) the border B t 1 is a cover if and only if GAP(t 1) is empty. Checking whether or not GAP is empty can be done in constant time, by keeping GAP(k); GAP(k 1); :::; GAP(t 1) as a doubly linked list.

Theorem 6.1 Algorithm 6.1 checks whether B i ; for all 1 t k, covers the matrix T in O(n 2 + R), where R is the number of ranges. Step 4 has also a one to one relationship with the number of ranges, also requiring O(R) time. One can easily deduce that steps 5.1-5.5 require O(1) operations each, for adding and deleting items in doubly linked lists; the total number of operations of Step 5 is also bounded by O(R).

Computing The Ranges

Recall, that each position p; q] of T is associated with a range p; q; l; r] if and only if the position p; q] is within the rst column of an occurrence of all of the following borders B l ; B l+1 ; :::; B r , but the position p; q] is not within the rst column of an occurrence of either B l 1 or B r+1 . Let B j denote the rst column of the border B j , for some j = 1; :::; k. Also, we say that a substring s of x, terminates at position j of x if and only if x j m + 1::j] = s 1::m], where m is the length of s. The computation of the ranges is based upon the following three simple facts: Fact 3. Let B v be the rst column of the largest border B v that terminates at position p; q] of T. Then B 1 ; B 2 ; :::; B v 1 are all terminating at p; q]. This follows from the fact that B j is a border of B v for j = 1; 2; :::; v 1 (see Figure 6-(i)). Let p j ; q], for j = 1; 2; :::; v, be the position that B j occurs as a su x of B v .

Fact 4. Suppose that there is no (non-empty) border whose rst column terminates at position p; q] of T and there is no (non-empty) border that occurs at p + 1; q]. If p; q; l; r] is a range for p; q], then p + 1; q; l; r] is a range for p + 1; q]. This follows from the fact that B j , for all j = l; l + 1; :::; r, covers the position p; q] of T, and since B j does not terminate at position p; q], for all j = l; l + 1; :::; r, it also covers p + 1; q] (See Figure 6-(ii)). Also,no new border occurs at p + 1; q]. Thus, in this case every range for p; q] is also a range for p + 1; q]. Fact 5. Let B v be the rst column of the largest border B v that terminates at position p; q] of T. The position p+1; q] of T is covered by B j , for some j = 1; :::; v, if and only if B j occurs in one of the following positions f p j + 1; q]; p j + 2; q]; :::; p + 1; q]g. The computation of the set LIST can also be done in O(n 2 ) units of time (in total) by preprocessing: for each occurrence of B j we pre-compute the nearest position in the same column that B j re-occurs; this is similar to step 4 of Algorithm 6.1 and preprocessing requires O(n 2 ) units of time.

All internal for loops go through all of the ranges in a column and the outer loop goes through all columns; since each of the if statements requires constant time, the loops require O(R) time.

Counting the Number of Ranges

We have seen that there are cases that two or more occurrences of a border can cover a position of T but they lead to just one range. For example, in Figure 6-(i), B 1 ; B 2 ; :::B v all cover p; q], but they de ne only one range p; q; 1; v]. In order to be able to count the ranges, we need to identify one of these occurrences, and we choose the one that is the closest to (and covers) the position whose range is in question; we say that these occurrences originate (establish) a range for that position. This will enable us to distinguish between originating and non-originating border occurrences and consequently count the number of ranges accordingly. Formally: Let p; q; l; r] be a range of the position p; q] of a square matrix T . There exists a position p 0 ; q] of T such that (i) The border B t of T occurs at p 0 ; q], with t such that l t r.

(ii) The position p; q] is within the occurrence of the border B t at p 0 ; q] (i.e., B t covers p; q]). (iii) There is no position p 00 ; q] of T , with p 00 > p with the above two properties.

We say that the border occurrence at position p 0 ; q] originates the range p; q; l; r] at p; q]. In Figure 6-(i), assuming that there no other borders occurring, the occurrence of B 1 (that terminates at p; q]) originates the range p; q; l; v].

The lemma below establishes the criteria under which, a border occurrence at a position originates a range. Lemma 6.3 Suppose that the borders B t and B s of T occur at the positions c; q]; e; q] of T and that the occurrence of B s at e; q] originates a range p; q; l; r] for position p; q]. The occurrence of B t at c; p] originates a range p; q; l 0 ; r 0 ] for position p; q] if and only if b t > p c and s < l 0 (6:1)

Proof . The border B t at c; p] originates a range at p; q] if and only if it covers p; q], that is p; q] is a position within the occurrence of B t at c; q] (see Figure 7

-(i)), hence b t > p c.
The occurrence of B t at c; q] implies that the borders B l 0 ; B l 0 +1 ; :::; B t cover p; q], where l 0 = C(p c). Similarly the occurrence B s at e; p] implies that the borders B l ; B l+1 ; :::; B s cover p; q], with l = C(p v). Thus B t originates a new range at p; q] if and only if s < l 0 = C(p c). [e ,q] q-th column

(ii) B [p,q] [c,q] . [e,q] (i) s l B B . .

Figure 7

The following lemma establishes an upper bound on the number of ranges originated by a chain of border occurrences. Lemma 6.4 Let e 1 ; q]; e 2 ; q]; :::; e m ; q] be the positions of the q-th column of T that a non-empty border of T occurs. Let d j = e j+1 e j ; j = 1; :::; m 1. If the occurrence at e j ; q] originates a range for e j+1 ; q] for every i = 1; :::; m 1, then d j 3 2 d j+1 (6:2) and the total number of ranges originated by these occurrences is O(n).

Proof . By induction on the number of occurrences. One can show that it holds for j = 5. Assume that positions e k+1 ; q]; e k+2 ; q]; :::; e m ; q] satisfy (6.2); we will next show e k ; q]; e k+1 ; q]; :::; e m ; q] also satisfy (6.2) Let x j , j = 1; 2; 3; 4, be the string that starts at position e k j+1 ; q] and has length d k j+1 (see Figure 7-(ii)). From Lemma 6.3 and (6.1) follows that jx j j > jx j+1 j and therefore x j+1 is a pre x of x j , for j = k; :::; m 1. Using the facts that x 2 is a pre x of x 1 , x 3 is a pre x of x 2 and x 4 is a pre x of x 3 (see Figure 7-(ii)), one can nd strings c; f; g; h such that x 1 = cfgh x 2 = cfg x 3 = cf x 4 = c Also let z 1 = cfghcfgcfc z 2 = cfgcfc z 3 = cfc z 4 = c be the substrings of the q-th column of T starting at positions e k ; q]; e k+1 ; q]; e k+2 ; q] and e k+3 ; q] respectively and terminating at e k+4 ; q] Case of g < c: From Lemma 6.3 and (6.1) follows that z 3 is a pre x of z 2 , hence we have that c = gs for some string s. From z 1 and z 2 above one can see that x 2 s is a pre x of hx 2 x 3 . If jhj jx 2 j=2 then we have that x 2 = h h 0 ; for some pre x h 0 of h and integer 2 which implies c = h h 00 , for some integer < and some pre x h 00 of h and which in turn implies at least another border occurrence aoriginating a range at the position e k+2 jcj + 1; q] between e k+1 ; q] and e k+2 ; q], a contradiction. Thus we have jhj > jx 2 j=2 ! d k = jx 1 j = jx 2 j + jhj > 3

2 d k+1
Case of g c. This is similar to the case above. We have shown that (6.2) holds and furthermore one can observe that border occurrences at positions e 1 ; q]; e 2 ; q]:::; e j ; q] originate j ranges to positions between e j ; q] and e j+1 ; q], or jd j in total for that region. The total number of ranges is m j=1 jd j m j=1 j( 2 3 ) j 1 d 1 = O(n) Theorem 6.5 The cardinality of the list of ranges created in each column is O(n).

Thus the total number of ranges R = O(n 2 ).

Proof . Let e 1 ; q]; :::; e m ; q] be the positions of the q-th column of T that a non-empty border of T occurs. The worst case arises when the occurrence at e i ; q], i = 1; :::; m 1 originates ranges to all the positions below it, i.e., e j ; q], j = i+1; :::; m 1. Thus from Lemma 6.4, the number of ranges is at most O(n) for each column of T or R = n 2 . Theorem 6.6 Algorithm 6.1 computes all square covers of a square matrix T in linear time.

Proof It follows from Theorem 6.5 and Theorem 6.1.

Conclusion and Open Problems

The Aho-Corasick Automaton depends on the alphabet; it is an open question whether the all-covers of a square matrix can be computed in linear time independent of the alphabet. A natural extension of the problems presented here is the design of algorithms for computing rectangular covers for rectangular matrices. Another extension of the above problem is that of computing approximate covers that allow the presence of errors.

Also of interest is the PRAM complexity of both pre x string matching and all covers problems (on square and rectangular matrices). An optimal PRAM algorithm for computing the smallest cover was given in IK96] but the optimal computation of all covers is still an open problem (see IK96b]). In particular the PRAM relationship between the pre x string matching problem and the computation of the diagonal failure function; the PRAM computation of the failure function (see GP94]) was done using the pre x string matching algorithm, the reverse way of the methods used here.

  Figure 1The Aho-Corasick Automaton for fabca; aabc; acba; aacag. Trivial failure links, i.e., failure links to the initial state, are not shown. Non-trivial failure links are shown as dotted lines. Final states are shown as patterned squares.

  Figure2

  4.1 computes the diagonal failure function of an n n matrix in O(n 2 ) time.

  Construct the Aho-Corasick automata for R and C; Compute the diagonal failure function f of P; for d = 1 to n do k 0; for i = d to n do r i;d T i; i d + 1] T i; 1]; c i;d T d; i d + 1] T d; i d + 1]; comment See Figure 4 for illustration of r i;d and c i;d : while pre x k+1 (r i;d ) 6 = r 0 k+1 or pre x k+1 (c i;d ) 6 = c 0 k+1 do comment The condition is tested as in corollary 2.4. p(i k; d) k; comment The integer p(i k; d) is the length of the largest pre x of the pattern occurring at position i k; i k d + 1]. k fAlgorithm 5.1 computes the longest pre x of the m m matrix P occurring at every position of an n n matrix T in O(n 2 + m 2 ) time. Proof . The computation of the diagonal failure function of P requires O(m 2 ) time. The computation of the Aho-Corasick automata requires O(n 2 + m 2 ) time. The theorem follows from corollaries 2.3 and 2.4.

  Proof .Step 1 and Step 2 require O(n 2 ) operations by Theorems 4.1 and 5.1. The computation of the ranges in Step 3 is shown next (Theorem 6.2) and it requires O(R) time.

Partially supported by SERC grants GR/F 00898 and GR/J 17844, NATO grant CRG 900293, ESPRIT BRA grant 7131 for ALCOM II, and MRC grant G 9115730. Supported by a Medical Research Council Studentship.

The main steps of the computation of the ranges are as follows: Assume that we have computed all ranges for positions i; q] for i = 1; 2; :::; p, for the q-th column of T, and we proceed to compute the ranges for position p + 1; q] of T. Let B t be the largest border that occurs at p + 1; q]. We consider two cases:

1. There is no border that terminates at p; q]. In this case the borders that cover p; q], also cover p + 1; q] (Fact 4). Therefore, for each range p; q; l; r], we create one of the following new ranges: either p + 1; q; 1; r] (when l t r ) or p + 1; q; 1; t] (when t > r) or p + 1; q; l; r] and p + 1; q; 1; t] (when t < l). This follows from Fact 4 combined with the fact that B t occurs at position p + 1; q] of T. 2. Let B v be the largest border whose rst column terminates at p; q]. Let p j ; q], for j = 1; 2; :::; v, be the position that B j ; occurs as a su x of B v . For j = 1; 2; :::; v, we check whether there is another occurrence of B j in positions below p j ; q] and above of p + 2; q] . If such an occurrence does not exist, then we insert j into a set named LIST. From Fact 5, the members of the set LIST are the indices of borders that do not cover p + 1; q], hence for each range p; q; l; r], we create ranges p + 1; q; l; s 1 1] , p + 1; q; s j 1; s j+1 1], j = 2; 3; :::; m 1 and p + 1; q; s m 1; r], for all s i 2 LIST : l s 1 < s 2 < ::: < s m < r. These ranges now need to be modi ed to take into the account the occurrence of B t at p + 1; q], in an identical manner to step 1 above. The pseudo-code below provides a detailed account of the computation of the ranges. Algorithm 6.2 begin for j = 1 to n do if B t occurs at position 1; j] then create the range 1; j; 1; t]; od for v = 1 to k do TERMINATE p; q] v, for all positions p; q] in T that B v occurs; od for q = 1 to n do for p = 1 to n do Let B t be that largest border that occurs at position p + 1; q]; if TERMINATE p; q] = ; then for all ranges p; q; l; r] of position p; q] do if l t r then create the range p + 1; q; 1; r]; if t > r then create the range p + 1; q; 1; t]; if t < l then create the ranges p + 1; q; 1; t] and p + 1; q; l; r]; od if TERMINATE p; q] = v then for j = 1 to v do if B j does not occur between positions p b j + 2; q] and p + 1; q] then add j to the LIST od for all ranges p; q; l; r] associated with p; q] do Compute fs i 2 LIST : l s 1 < s 2 < ::: < s m < rg;

Create ranges p + 1; q; l; s 1 1], p + 1; q; s m 1; r] and p + 1; q; s j 1; s j+1 1], j = 2; 3; :::; m 1; od for all ranges p + 1; q; l; r] of position p + 1; q] do if l t r then create the range p + 1; q; 1; r]; if t > r then create the range p + 1; q; 1; t]; if t < l then create the ranges p + 1; q; 1; t] and p + 1; q; l; r]; od od od end. Theorem 6.2 Algorithm 6.2 computes all ranges in O(n 2 + R) time.

Proof . The computation of the list TERMINATE takes at most O(n 2 ) units of time.


Maxime Crochemore

Filippo Mignosi

Antonio Restivo

Automata and Forbidden Words

Keywords: formal languages, factorial language, anti-factorial language, factor code, factor automaton, forbidden word, avoiding a word, failure function

Introduction

Let L A be a factorial language, i.e., a language containing all factors of its words. A word w 2 A is called a minimal forbidden word for L if w = 2 L and all proper factors of w belong to L. We denote by MF(L) the language of minimal forbidden words for L.

The study of combinatorial properties of MF(L) helps investigate the structure of the language L or of the system it describes. For instance, locally testable factorial languages (cf 8]) are characterized by the fact that the corresponding languages of minimal forbidden words are nite. In the context of Symbolic Dynamics they correspond to systems of nite type.

Another example is given by a language L that is the set of factors of an in nite word: in this case, as shown in 2], the elements of MF(L) are closely related to the bispecial factors (cf. 6], 7] and 3]) of the in nite word.

A preliminary version of this work has been accepted to MFCS'98 y Institut Gaspard-Monge, mac@univ-mlv.fr. Work by this author is supported in part by Programme \G enomes" of C.N.R.S.

z Universit a di Palermo, mignosi@altair.math.unipa.it.

x Universit a di Palermo, restivo@altair.math.unipa.it.

1

A measure of complexity of the language L is introduced in 2] based on the function F L , that counts, for any n, the number of words of length n in MF(L). Authors prove that the growth of F L (n) as well as the topological entropy of MF(L) are topological invariants of the dynamical system de ned by L. This result provides a usefull tool to show that some systems are not isomorphic, which comes in addition to other notions like the ordinary notion of entropy and the zeta function, for example.

Finally, 5] considers properties of languages de ned by nite forbidden sets of words. Authors de ne the M obius function for these languages.

In this paper we focus on the transformations between L and MF(L). We rst design an automaton accepting L and that is built from the language M = MF(L). When M is a nite set the transformation is e ective. Moreover, if M is given by its digital tree, that is, its tree-like deterministic automaton, the algorithm is very similar to the algorithm of Aho and Corasick that builds a pattern-matching machine for a nite set of words 1].

In a second part we consider the particular situation of a language that is the set of factors of a single word v. The construction of its factor automaton, the minimal deterministic automaton accepting the factors of v (see 4]) is known to be rather intricate. It is remarkable that the preceding transformation yields exactly the factor automaton of v when the input if the set M of minimal forbidden words of v. We also give an algorithm that realizes the converse transformation, building the trie of M from the factor automaton of v. A corollary of the algorithm is a non-trivial upper bound on the number of minimal forbidden words of a word.

The complexities of algorithms described in this paper are all linear in the size of their input or output. Therefore, the design of possible faster algorithms relies on di erent representations of objects, which is not the aim of the paper.

Avoiding an anti-factorial language

Let A be a nite alphabet and A be the set of nite words drawn from the alphabet A, the empty word included. Let L A be a factorial language, i.e. a language satisfying: 8u; v 2 A uv 2 L =) u; v 2 L. The complement language L c = A n L is a (two-sided) ideal of A . Denote by MF (L) the base of this ideal, we have L c = A MF (L)A .

The set MF(L) is called the set of minimal forbidden words for L. A word v 2 A is forbidden for the factorial language L if v = 2 L, which is equivalent to say that v occurs in no word of L. In addition, v is minimal if it has no proper factor that is forbidden.

One can note that the set MF (L) uniquely characterizes L, just because L = A n A MF (L)A :

(1) The following simple observation provides a basic characterization of minimal forbidden words.

Remark 1 A word v = a 1 a 2 a n belongs to MF (L) i the two conditions hold: v is forbidden, (i.e., v = 2 L), both a 1 a 2 a n 1 2 L and a 2 a 3 a n 2 L (the pre x and the su x of v of length n 1 belong to L). The remark translates into the equality:

MF (L) = AL \ LA \ (A n L):
(2) As a consequence of both equalities (1) and (2) we get the following proposition.

Proposition 1 For a factorial language L, languages L and MF (L) are simultaneously rational, that is, L 2 Rat(A ) i MF (L) 2 Rat(A ).

The set MF (L) is an anti-factorial language or a factor code, which means that it satis es: 8u; v 2 MF (L) u 6 = v =) u is not a factor of v, property that comes from the minimality of words of MF (L).

We introduce a few more de nitions.

De nition 1 A word v 2 A avoids the set M, M A , if no word of M is a factor of v, (i.e., if v = 2 A MA ). A language L avoids M if every word of L avoids M. From the de nition of MF (L), it readily comes that L is the largest (according to the subset relation) factorial language that avoids MF (L). This shows that for any anti-factorial language M there exists a unique factorial language L(M) for which M = MF (L). The next remark summarizes the relation between factorial and anti-factorial languages.

Remark 2 There is a one-to-one correspondence between factorial and antifactorial languages. If L and M are factorial and anti-factorial languages respectively, both equalities hold: MF (L(M)) = M and L(MF(L)) = L.

We also refer to the next de nition that is to be considered in the context of dynamical systems (see 9] for example).

De nition 2

The factorial language L is said to be of nite type when MF (L) is nite.

Finally, with an anti-factorial nite language M we associate the nite automaton A(M) as described below. The automaton is deterministic and complete, and, as shown at the end of the section by Theorem 3, the automaton accepts the language L(M).

The automaton A(M) is the tuple (Q; A; i; T; F) where the set Q of states is fw j w is a pre x of a word in Mg, A is the current alphabet, the initial state i is the empty word , the set T of terminal states is Q n M. States of A(M) that are words of M are sink states. The set F of transitions is partitioned into the three (pairwise disjoint) sets F 1 , F 2 , and F 3 de ned by: F 1 = f(u; a; ua) j ua 2 Q; a 2 Ag (forward edges or tree edges), F 2 = f(u; a; v) j u 2 Q n M; a 2 A; ua = 2 Q; v longest su x of ua in Qg (backward edges), F 3 = f(u; a; u) j u 2 M; a 2 Ag (loops on sink states). The transition function de ned by the set F of arcs of A(M) is noted . Remark 3 One can easily prove from de nitions that 1. if q 2 Q n (M f g), all transitions arriving on state q are labeled by the same letter a 2 A, 2. from any state q 2 Q we can reach a sink state, i.e., q can be extended to a word of M.

De nition 3 For any v 2 A , q v denotes the state ( ; v), target of the unique path in A(M) starting at the initial state and labeled by v.

Since A(M) is a complete automaton, q v is always de ned. In the automaton A(M) states are words, but to avoid misunderstandings we sometimes write \the word corresponding to q v " instead of just \the word q v ".

Remark 4 Note that if v is a state of A(M) we have q v = v.

We are now ready to state and prove the next lemma that is used in the proof of Theorem 3, the main result of the section.

Lemma 2 Let M be an anti-factorial language and consider A(M). Let v 2 A be such that, for any proper pre x u of v, q u is not a sink state (q u = 2 M). Then, 1. the word q v is a su x of v, 2. q v is the longest su x of v that is also a state of A(M) (or 8q 2 Q q su x of v =) q su x of q v ). Proof. By induction on jvj.

Base of the induction, jvj = 0. Then, v = = q v and points 1 and 2 are trivially satis ed.

Inductive step jvj > 0. We can write v = ua; a 2 A; hence, q v = (q u ; a) or equivalently (q u ; a; q v ) 2 F. By induction, q u is a su x of u and, if q 2 Q is a su x of u, q is also a su x of q u . By hypothesis, the transition (q u ; a; q v ) cannot belong to F 3 because q u is not a sink state. We have two cases:

(i) (q u ; a; q v ) 2 F 1 , (ii) (q u ; a; q v ) 2 F 2 .

In case (i) condition 1 readily comes from the inductive hypothesis because q v = (q u ; a). Let us suppose that q is a state su x of v. If q = then 2 is trivially satis ed; otherwise, if q 6 = , q = (q 0 ; a) for some state q 0 2 Q. Since v = ua, q 0 is a su x of u and, by induction, q 0 is a su x of q u . Since q v = (q u ; a) and q (= (q 0 ; a)) is a su x of q v , which proves that 2 is satis ed. In case (ii), since by de nition q v is a su x of (q u ; a), and since by induction q u is a su x of u, q v is a su x of ua = v and 1 holds. If q 2 Q is a su x of v with q 6 = (otherwise 2 trivially holds), then q = q 0 a for some q 0 su x of u, and by induction q 0 is a su x of q u and moreover q is a su x of (q u ; a). By de nition q v is the longest su x of (q u ; a) that is also a state, and consequently q is a su x of q v .

./

Denoting by Lang (A) the language accepted by an automaton A, we get the main theorem of the section.

Theorem 3 For any anti-factorial language M, Lang (A(M)) = L(M).

Proof. We rst prove L(M) Lang (A(M)). We have to show that if v is a word that avoids M then v 2 Lang (A(M)). Assume ab absurdo that v = 2 Lang (A(M)); therefore q v is a sink state. Let u be the shortest pre x of v for which q u is a sink state (note that q u = q v ). By lemma 2 statement 1, q u is a su x of u, but q v is by de nition an element of M, and so v does not avoid M, a contradiction.

We then prove Lang (A(M)) L(M). Let v 2 Lang (A(M)). Let us suppose ab absurdo that v does not avoid M, i.e., v = uwz for some w 2 M; u; z 2 A . We choose uw as the shortest pre x of v that belongs to A M. Since w 2 M it is by de nition a state of A(M); since w is a state that is a su x of uw, by Lemma 2 statement 2, w is a su x of q uw . But q uw , which is by de nition a state of A(M), is a pre x of an element w 0 of M (note that w 0 is not empty).

Since w is a su x of a pre x of w 0 , w is a factor of w 0 , a contradiction because M is anti-factorial.

./

The above de nition of A(M) turns into the algorithm below, called Lautomaton, that builds the automaton from a nite anti-factorial set of words.

The input is the trie T that represents M. It is a tree-like automaton accepting the set M and, as such, it is noted (Q; A; i; T; 0 ). The procedure can be adapted to test whether T represents an anti-factorial set, or even to generate the trie of the anti-factorial language associated with a set of words.

In view of Equality 1, the design of the algorithm remains to adapt the construction of a pattern matching machine (see 1] or 4]). The algorithm uses a function f called a failure function and de ned on states of T as follows. States of the trie T are identi ed with the pre xes of words in M. For a state au (a 2 A, u 2 A ), f(au) is 0 (i; u), quantity that may happen to be u itself.

Note that f(i) is unde ned, which justi es a speci c treatment of the initial state in the algorithm. Example. Figure 1 displays the trie that accepts M = faa; bbab; bbbg. It is an anti-factorial language. The automaton produced from the trie by algorithm L-automaton is shown in Figure 2. It accepts the pre xes of (ab b)(ab) ba that are all the words avoiding M.

Theorem 4 Let T be the trie of an anti-factorial language M. Algorithm Lautomaton builds a complete deterministic automaton accepting L(M).

Proof. The automaton produced by the algorithm has the same set of states as the input trie. It is clear that the automaton is deterministic and complete.

Let u 2 A + and p = (i; u). A simple induction on juj shows that the word corresponding to f(p) is the longest proper su x of u that is a pre x of some word in M. This notion comes up in the de nition of the set of transitions F 2 in the automaton A(M). Therefore, the rest of the proof just remains to check that instructions implement the de nition of A(M). 3 Factor automaton of a single word

In this section we specialize the previous results to the language of factors of a single word. It is proved below that the contruction of Section 2 yields the factor automaton (minimal deterministic automaton accepting the factors) of the word (see Theorem 7). The minimality of the automaton seems to be exceptional because, for example, the same construction applied to the set faa; abg does not provide a minimal automaton. The reverse construction that produces the trie of minimal forbidden words from the factor automaton is described in the next section.

We consider a xed word v 2 A and denote by F(v) the language of factors of v. Proposition 6 The language F(v) is of nite type.

Proof. Indeed, factors of v, of lengths less than jvj+1, avoid all words of length exactly jvj + 1. Therefore, every minimal forbidden word of F(v) has length at most jvj + 1.

./ For instance, for the word v = abbab, the set of minimal forbidden words of F(abbab) is faa; aba; babb; bbb; cg (see Figures 3 and4).

The result of the previous proposition is made more precise in the next section, but an immediate consequence of it and of the de nition of the automaton A(M) for an anti-factorial language M, the automaton A(MF (F(v))) has a nite number of states. The next statement gives a complete characterization of the automaton as the factor automaton of v.

Theorem 7 For any v 2 A , the automaton obtained from A(MF (F(v))) by removing its sink states is the minimal deterministic nite automaton accepting the language F(v) of factors of v. Proof. The automaton A(MF(F(v))) is already a deterministic nite automaton that accepts the language F(v) by Theorem 3. We only have to prove that it is minimal after removing the sink states.

Suppose ab absurdo that there exist two equivalent non-sink states p; q in Q. By the standard equivalence relation of undistinginshability and by construction p; q 2 F(v). Hence, v = xpy and v = x 0 qy 0 and we can choose x and x 0 of minimal length. We consider two cases:

(i) jxpj 6 = jx 0 qj, (ii) jxpj = jx 0 qj. Case (i). We can suppose for example that jxpj < jx 0 qj (the case jxpj > jx 0 qj is handled symmetrically). Then, xpy 2 F(v) implies that (p; y) is not a sink state, hence, by the equivalence (q; y) is not a sink state, that is, qy 2 F(v) by Remark 4. Therefore, v = x"qyz where jx"j jx 0 j by the choice of x 0 (of minimal length). Hence, jvj jx 0 j + jqj + jyj + jzj > jxpj + jyj = jvj, a contradiction.

Case (ii). The equality jxpj = jx 0 qj implies either that p is a su x of q or the converse. Let us suppose for example that p = sq for some word s 6 = . By Remark 3 statement 2, there exists w = pz that belongs to MF (F(v)). By the equivalence, qz is also a sink state and, again by the equivalence, for no proper pre x u of qz, q u is a sink state. Hence, by Lemma 2.1, q qz is an element of MF (F(v)), that is, a su x of qz. Since p = sq; s 6 = , q qz is a proper su x of pz against the anti-factorial property of MF (F(v)). A contradiction again.

After cases (i) and (ii) it appears that there cannot exist two di erent nonsink states p; q in Q that are equivalent. Therefore the automaton without sink states is minimal, which ends the proof.

./ The property stated by Theorem 7 does not generalize to any nite set words.

For example, consider the set M = faa; bag. Its trie has three internal nodes and then the automaton A(M) has three states after removing sink states. But the language L(M) is b + ab and its minimal automaton has only two states. else if (p; a) = q and q not already treated 5. set 0 (p; a) = q;

Minimal forbidden words of a word

6. return (Q; A; i; fsinksg; 0 );

The input of algorithm MF-trie is the factor automaton of word v. It is the minimal deterministic automaton accepting the factors of v. It includes the failure function de ned on the states of the automaton and called s. This function is a by-product of e cient algorithms that build the factor automaton (see 4]). It is de ned as follows. Let u 2 A + and p = (i; u). Then, s(p) = (i; u 0 ) where u 0 is the longest su x of u for which (i; u) 6 = (i; u 0 ). It can be shown that the de nition of s(p) does not depend on the choice of u.

Example Consider the word v = abbab on the alphabet fa; b; cg. Its factor automaton is displayed in Figure 3. The failure function s de ned on states has values: s(1) = s(5) = 0, s(2) = s(3) = 5, s(4) = 1, s(6) = 2. Algorithm MF-trie produces the trie of Figure 4 that represents the set of ve words faa; aba; babb; bbb; cg.

Theorem 8 Let A be the factor automaton of a word v 2 A . (It accepts the language F(v).) Algorithm MF-trie builds the tree-like deterministic automaton accepting the set of minimal forbidden words of F(v), that is MF(F(v)).

Proof. The transitions de ned at line 5 duplicates the transition of the widthrst search tree, which is the tree of shortest paths from the the initial state of A. This fact is used in the proof. All other transitions are created at line 3 and lead to a sink state. Let A 0 be the automaton produced by the algorithm. Consider a word ua (a 2 A) accepted by A 0 . (A 0 accepts only non-empty words.) Let p = 0 (i; u). By the remark above, u is the shortest word for which (i; u) = p. Therefore, if u = by with b 2 A, we have (i; y) = s(p) by de nition of the su x function s. When the test \ (s(p); a) de ned" is satis ed, this implies that ya 2 F(v). Thus, bya 6 2 F(v), while by; ya 2 F(v). So, after Remark 1, bya = ua is a minimal forbidden word for F(v).

If u is the empty word, p = i. The transition from i to the sink labeled by a is created under the condition \ (p; a) unde ned", which means that the letter a does not occur in v. The word a is again a minimal forbidden word for F(v) in this case. This proves that any word accepted by A 0 is in MF (F(v)). Conversely, let ua 2 MF (F(v)). If u is the empty word, this means that a does not occur in v, therefore there is no transition labeled by a in A. Lines 3 and 4 cope with this situation by creating a 0 -transition from the initial state to accept a.

Assume now that u = by with b 2 A. The word u is a factor of v, so let p = (i; u). Note that u is the shortest word for which p = (i; u), because all such words are su xes of each others in the factor automaton A. The word ua is not a factor of v, so the condition \ (p; a) unde ned" is satis ed. Let q = s(p). We have q = (i; y) because of the minimality of length of u and the de nition of s. By the choice of ua = bya, ya is a factor of v. Thus, the condition \ (s(p); a) de ned" at line 3 is satis ed which yields the creation of a transition at line 4 to make A 0 accept ua as wanted. This ends the whole proof.

./ Corollary 9 A word v 2 A has no more than 2(jvj 2)(jA v j 1)+jAj minimal forbidden words if jvj 3, where A v is the set of letters occurring in v. The bound becomes jAj + 1 if jvj < 3.

Proof. The number of words in MF (F(v)) is the number of sink states created during the execution of algorithm MF-trie. These states have exactly one

Figure 1 :

 1 Figure 1: Trie of the factor code faa; bbab; bbbg on the alphabet fa; bg. Squares represent terminal states.

Figure 2 :

 2 Figure 2: Automaton accepting the words that avoid the set faa; bbab; bbbg.Squares represent non-terminal states (sink states).

Figure 3 :Figure 4 :

 34 Figure 3: Factor automaton of abbab; all states are terminal.

ingoing arc originated at a state of the factor automaton A of v. So, we have to count these arcs.

From the initial state of A there is exactly jAj jA v j such arcs. From the (unique) state of A without outgoing arc, there are at most jA v j such arcs. From other states there are at most jA v j 1 such arcs.

For jvj 3, it is known that A has at most 2jvj 2 states (see 4]). Therefore, jMF(F(v))j (jAj jA v j)+jA v j+(2jvj 4)(jA v j 1) = 2(jvj 2)(jA v j 1)+jAj.

When jvj < 3, it can be checked directly that jMF(F(v))j jAj + 1. ./ Proposition 10 Algorithm MF-trie runs in time O(jvj jAj) on input word v if transition functions are implemented by transition matrices.

Proof. As for the proof of Proposition 5, the hypothesis on implementation implies that the running time of the algorithm is proportional to jQj jAj. Thus, the result is a consequence of the linear size of A: the factor automaton of v has no more than 2jvj states (see 4] for instance).

./