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

Maxime Crochemore

Gabriele Fici
email: fici@univ-mlv.fr

Presentations of Constrained Systems with Unconstrained Positions

We give a polynomial-time construction of the set of sequences that satisfy a finite-memory constraint defined by a finite list of forbidden blocks, with a specified set of bit positions unconstrained. Such a construction can be used to build modulation/error-correction codes (ECC codes) like the ones defined by the Immink-Wijngaarden scheme in which certain bit positions are reserved for ECC parity. We give a lineartime construction of a finite-state presentation of a constrained system defined by a periodic list of forbidden blocks. These systems, called periodic-finite-type systems, were introduced by Moision and Siegel. Finally, we present a linear-time algorithm for constructing the minimal periodic forbidden blocks of a finite sequence for a given period.

Index Terms-Directed acyclic word graph (DAWG), finitememory systems, finite-state encoders, forbidden blocks, maximum transition run (MTR) codes, modulation codes, periodicfinite-type (PFT) systems, run-length limited (RLL) codes.

I. INTRODUCTION

Recording systems often use combined modulation/errorcorrection codes (ECC codes). While error-correction codes enable the correction of a certain number of channel errors, modulation codes encode the sequences into a constrained channel that is supposed to reduce the likelihood of errors.

), proposes to encode an unconstrained sequence of bits into a constrained sequence in which certain bit positions are reserved for ECC parity. The bit values in these positions can be flipped (or not flipped) independently without violating the constraint. These positions are called unconstrained positions. Therefore, ECC parity information can be inserted into the unconstrained positions of the modulation-encoded sequences without making them out of the constrained channel.

, the authors study different approaches to build such codes, one of them being based on the construction of the unique maximal subsystem of a constrained system S such that any position modulo T in U is unconstrained, where

U is a given subset of integers modulo some integer T . We call this system the (U, T )-unconstrained subsystem of S. The knowledge of this maximal subsystem enables the computation of the maximal possible rate of a code that both satisfies a given constraint and is unconstrained in a specified set of positions. Indeed, this maximal rate is the Shannon capacity of the maximal subsystem. It also enables to apply standard modulation code constructions to this subchannel [4]. Since these code constructions work on a presentation of the subchannel, it is worth to efficiently compute a small presentation of this subchannel.

In this correspondence, we focus on the construction of this maximal subsystem for a finite-state constrained system with finite memory. Our goal is to reduce the time and space complexities of the general solution proposed in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF]. We consider a finite-memory constrained system S defined by a finite list of forbidden blocks. Given such a system and a subset U of integers modulo some integer T , we construct in a polynomial amount of time and space a finite-state graph that presents the (U, T )-unconstrained subsystem of S.

The maximal subsystem appears to be a natural example of periodic-finite-type systems (PFT) introduced by Moision and Siegel in [5]. This was already noticed in [3, pp. 869].

In our process, we start with the construction of a periodic list of forbidden blocks that defines the maximal subsystem from a finite list of forbidden blocks of the finite-memory system. More precisely, if the input data is a trie T representing a finite prefix-free list of forbidden blocks, the algorithm works in space and time O(T × |A| × |T | × log |T |), where |T | is the size (the number of states) of the trie and A is the alphabet. In a second step, we construct in linear time and space a finite-state presentation of a periodic-finite-type shift defined by a periodic list of forbidden blocks. The whole two-step process computes a finite-state presentation of the maximal unconstrained subsystem. Moreover, our algorithm becomes linear if the input trie has itself a linear structure. For instance, it runs in O(j) time for the MTR(j) constraint, and in O(k) time for the RLL (d, k) constraint with the input data d, k(d ≤ k), if the period T of the unconstrained positions is naturally assumed to be constant. We restrict ourselves to binary systems, but the results carry over easily to constrained finite-memory systems over any finite set of symbols.

While our algorithm is polynomial and the algorithm given in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF] is exponential in the general case, they cannot be compared directly for the following reasons. The algorithm described in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF] works in an exponential amount of space and time for all finite-state systems given by a finite-state presentation, and in quadratic space and time for finitememory systems with an additional condition called the gap condition. The gap condition limits the number of unconstrained positions relatively to the memory of the system. An efficient algorithm is also proposed in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF] for the special case of MTR systems. We point out that, although our algorithm has a better complexity for finite-memory systems, and no restriction similar to the gap condition, it works with different input data. Indeed, it is possible to compute in polynomial time an automaton accepting a list of forbidden blocks of a finite-memory system given by a deterministic automaton with a single initial state [START_REF] Béal | Computing forbidden words of regular languages[END_REF]. But it is not possible to do it in polynomial time from a presentation where all states are initial ones. Thus our algorithm runs faster if the input data are a list of forbidden blocks while the one presented in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF] is more efficient if both the input data are a presentation of the constraint and the gap condition is satisfied.

Our correspondence is organized as follows. In Section II, we recall some background regarding constrained systems with unconstrained positions, which are introduced in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF] ]. In Section III we give a linear construction of a finite-state presentation of a periodic-finite-type shift defined by a periodic list of forbidden blocks. In Section IV, we combine the algorithm given in Section III to a preliminary treatment of the input trie presenting a list of forbidden blocks of the constrained channel. Although it is not directly related to modulation/error-correction codes construction, we added a final section which provides a linear space and time computation of minimal periodic forbidden blocks of a finite sequence for a given period. This algorithm extends a known algorithm from [7] for computing the minimal forbidden blocks of a finite word, which is used in a lossless data compression scheme [8]. We also believe that the notion of periodic list of forbidden blocks introduced by Moision and Siegel can be used in many areas other than modulation/error-correction codes.

II. BACKGROUND AND BASIC DEFINITIONS

We recall definitions that can be found in [9]. Let A = {0, 1, . . . , k} be a finite alphabet, with k ≥ 1. We denote by A * the set of finite words on A, by A Z the set of bi-infinite sequences

x = • • • x -3 x -2 x -1 x 0 x 1 x 2 x 3 • • • drawn from A,
and by A N the set of right-infinite ones. The shift map σ transforms a sequence (x i ) i∈Z into the sequence (x i+1 ) i∈Z . If i ≤ j are integers, we denote by x[i . . j] the factor or subblock x i . . . x j of a finite or infinite word x. A finite word w is a subblock of a finite or infinite word x at position i

if w = x[i . . i + |w| -1],
where |w| is the length of w. We denote this fact by w

≺ i x. Note that w = w[0 . . |w| -1].
An automaton is a finite labelled multigraph (or simply a graph). It is a tuple (Q, A, E), where Q is a finite set of states, A is the labeling alphabet, and E is a finite set of edges labelled with elements in the alphabet A. An automaton accepts a set of finite words when initial and final states are specified. A finite word is then accepted if it is the label of a finite path from an initial state to a final one. The set of bi-infinite labels of paths in an automaton is called a constrained system, or also a sofic shift in the symbolic dynamics terminology. The automaton is then called a presentation of the shift. In that case, the initial and final states may not be specified since all states are supposed to be both initial and final.

F (0) = {1}, F (1) = ∅.
An automaton is deterministic if for any given state and any given symbol, there is at most one outgoing edge labelled by a given symbol. A sofic shift is irreducible if it has a presentation with a strongly connected graph. In an essential presentation all states have at least one outgoing edge and one incoming edge. An automaton has finite memory M (or also is M -local or M -definite) if whenever any two paths of the automaton of length M have the same label sequence, they end at the same state. Finite-memory systems or finite-type systems or shifts of finite type (SFT) have a finite-memory presentation. Examples of such systems include the RLL and MTR constraints.

Finite-type shifts are characterized by a finite collection of forbidden blocks. If F is a finite subset of A * , we denote by X F the shift of finite type defined by the set of forbidden words F . A bi-infinite word x belongs to X F if and only if w ≺ i x, for some index i, implies w / ∈ F. Any irreducible sofic shift has a unique minimal deterministic presentation called the right Shannon cover of the shift.

Periodic-finite-type shifts are constrained systems with a time-varying constraint. They have been introduced by Moision and Siegel in [5]. They provide suitable representations of constrained systems that forbid the appearance of certain patterns in a periodic manner.

Let T be a positive integer, called the period. Let F be a finite collection of finite words over A, where each w i ∈ F is associated with an integer n i in the set {0, 1 . . . T -1}, called the set of phases. The collection F is denoted by F = {(w 1 , n 1 ), . . . , (w |F | , n |F | )} and called a collection of periodic forbidden words. For 0 ≤ k < T , F (k) denotes the subset of F associated with the phase k. We denote by X {F ,T } the shift defined as the set of bi-infinite sequences having a shifted sequence that does not contain a word (w j , n j ) ∈ F starting at any index i = n j mod T . More precisely, a biinfinite word x belongs to X {F ,T } if and only if there is an integer k such that σ k (x) = y and, for each integer i, one has w ≺ i y ⇒ w / ∈ F (i mod T ) . A periodic-finite-type shift for a period T (PFT(T )) is a constrained system S such that there is a collection of periodic forbidden words F with S = X {F ,T } . A periodic-finite-type shift (PFT) is a PFT(T ) for some period T . An example is given in Figure 1.

Note that a shift of finite type is of periodic-finite-type for any period.

Constrained systems with unconstrained positions are defined in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF] as follows. Let S be a constrained system, T a positive period, and U ⊆ {0, . . . , T -1}, called the set of unconstrained positions. For any finite (resp. right-infinite, biinfinite) word x, a U -flip of x is a finite (resp. right-infinite, bi-infinite) word y such that y i = x i whenever i mod T / ∈ U . If A is the two-letter alphabet {0, 1}, a U -flip is obtained by flipping (or not) the bit values in the unconstrained positions. The set of all U -flips of words of a set X is called the Uclosure of X.

We denote by S U,T the set of all infinite (right-infinite or bi-infinite according to the context) sequences x of S such that • all U -flips of x belong to S, • x i = 1 for all positions i such that i mod T ∈ U . The unconstrained positions are forced to be 1 in order to fix a leader in each U -flip class of a word. The important fact is that one can independently change the values in the unconstrained positions without violating the constraint defined by S. Note that the shifted sequence of a sequence in S U,T may not be in S U,T (i.e. S U,T is not a shift). We denote the set of all these shifted sequences by S σ U,T . We also denote by S U,T σ the set of all bi-infinite shifted sequences of S σ U,T . Note that S σ U,T ⊆ S U,T σ .

An algorithm to compute a presentation of S U,T from a presentation of S is given in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF]. The result is a deterministic automaton G U,T whose graph has a period that is a multiple of T with the following properties:

• states of G U,T are partitioned according to T phases {0, . . . , T -1} in such a way that if a state has phase k, its successors have phase k + 1 mod T . • the transitions beginning in a state of a phase in U are labelled by 1. • S U,T is the set of right-infinite sequences of G U,T that are labels of a path starting in a state of phase 0. The link between constrained systems with unconstrained positions and periodic-finite-type shifts is given in the proposition below which is stated in [3, p. 869] without proof. We use the following notation: if U is a subset of {0, . . . , T -1}, and k is an integer, we denote by U +k the set {u+k mod T | u ∈ U }.

Proposition 1: Let S be a finite-type shift, T a period and U a set of unconstrained positions. The shifts S U,T σ and S σ U,T are PFT(T ) shifts.

Proof: Let F be a finite collection of finite forbidden words such that S = X F . We define two collections of periodic forbidden words G and G ′ as follows. k) and S σ U,T = X {G,T } . Let us detail for instance the equality S U,T σ = X {G ′ ,T } .

If k ∈ {0, . . . , T -1}, then G ′ (k) is the (U -k)-closure of F and S U,T σ = X {G ′ ,T -1} . If k ∈ U , then G (k) = {0} ∪ G ′ (k) . If k ∈ {0, . . . , T -1} \ U , then G (k) = G ′ (
Let x be a bi-infinite word of S U,T σ . Thus, there is an integer i with σ i (x) = y, and y belongs to the U -closure of S U,T . Thus y has a U -flip z in S. Let w be a finite block with w ≺ k y. There is a (U -k)-flip of w that is not in F . Thus w does not belong to the (U -k)-closure of F . This proves that S U,T σ ⊆ X {G ′ ,T } . Conversely, let x be a bi-infinite word of

X {G ′ ,T } .
There is an integer i with σ i (x) = y, and, for each integer k, one has w ≺ k y ⇒ w / ∈ G ′ (k mod T ) . Let z be a U -flip of y. Let w ′ be the block obtained from w with the same U -flip. Then w ′ ≺ k z. Since w does not belong to the (U -k)-closure of F , w ′ does not belong either. It follows that w ′ / ∈ F. Thus any U -flip of y belongs to S. Hence y belongs to the U -closure of S U,T , and

X {G ′ ,T } ⊆ S U,T σ .
Note that the result of the previous proposition extends as follows if S is a periodic-finite-type system for a period that is a multiple of T .

Proposition 2: Let S be a PFT(T ) shift, and U a set of unconstrained positions. The shifts S U,T σ and S σ U,T are unions of PFT(T ) shifts.

Proof: Suppose S = X {F ,T } . We first fix k 0 ∈ {0, 1, . . . , T -1}, and define the two collections of periodic forbidden words G k0 and G ′ k0 as follows.

If k ∈ {0, . . . , T - 1}, then G ′ (k) k0 is the (U -k)-closure of F (k+k0 mod T ) . Hence S U,T σ = k0∈{0,1,...,T -1} X {G ′ k 0 ,T } . If k ∈ U , then G (k) k0 = {0}∪G ′ (k) k0 . If k ∈ {0, . . . , T -1}\U , then G (k) k0 = G ′ (k) k0 . Hence S σ U,T = k0∈{0,1,...,T -1} X {G k 0 ,T } .
Let F be a list of periodic forbidden words of a shift X for a given positive period T . We say that F is periodic antifactorial if for any 0 ≤ i ≤ T -1, w ∈ F (i) implies that, for any proper factor u of w with u ≺ j w, u / ∈ F (i+j mod T ) . The notion of periodic anti-factorial list generalizes the notion of anti-factorial language (see for instance [7]). In the aperiodic case, an anti-factorial language means a language where no word is the factor of another one, while a factorial language is a language where each factor of a word of the language also belongs to the language (see [7]). In particular, the sets F (i) of an anti-factorial list F of periodic forbidden words are prefixfree codes, i.e. sets of words where no word is a proper prefix of another word of the set. The empty word never belongs to any F (i) .

Example 1 The list F (0) = {00, 11}, F (1) = {00, 11, 010} with T = 2 is periodic anti-factorial while the list F (0) = {00, 11, 010}, F (1) = {00, 10} with T = 2 is not. Indeed, in the latter list, 10 ∈ F (1) , 010 ∈ F (0) , and 10 ≺ 1 010.

Proposition 3: Let F be a list of periodic forbidden words of a PFT(T ) shift X. Then there is an anti-factorial list of periodic forbidden words F ′ of X with the same period, such that

F ′ (i) ⊆ F (i) for any 0 ≤ i ≤ T -1.
Proof: We define the list F ′ by

F ′ (i) = F (i) -F (i) A + -(A T ) + F (i) A * - T -1 j=1 (A T ) * A j F (i+j mod T ) A * ,
where A * denotes the set of all finite words over A and A + the set of all non-empty ones. Note that F ′ (i) is obtained from F (i) by removing all words that contain a strict factor in position k belonging to F (k+i mod T ) . By construction F ′ is periodic and anti-factorial, and X = X {F ′ ,T } .

The notion of anti-factorial list is weaker than the notion of minimal list of periodic forbidden words (see [5] for a notion of minimality, where minimal periodic forbidden words are called periodic first offenders). This notion is however a key point in the algorithms described in Section III.

III. COMPUTATION OF THE SHIFT DEFINED BY PERIODIC FORBIDDEN WORDS

In this section, we describe an algorithm that computes the shift X {F ,T } from a finite list of periodic forbidden words F with period T . This algorithm extends to the periodic case an algorithm of Crochemore et al. [7] that computes the language avoiding the blocks defined by an anti-factorial language. We first assume that the periodic forbidden list is anti-factorial, and show later how to remove this restriction.

We denote by B 0 (F , T ) the set of finite blocks w such that, for any integer

0 ≤ i ≤ |w|, u ≺ i w ⇒ u / ∈ F (i mod T ) . The set of finite blocks or factors of X {F ,T } is denoted by B(X {F ,T } ). Note that B 0 (F , T ) ⊆ B(X {F ,T } ). The inclusion is strict in general. For instance, if F (0) = {010}, F (1) = {101} and T = 2, 010 / ∈ B 0 (F , T ) since 010 ∈ F (0)
, and 010 ∈ B(X {F ,T } ).

Moreover, if w ∈ B(X {F ,T } ), there is a finite block u such that uw ∈ B 0 (F , T ). Hence B(X {F ,T } ) is included in the set of factors of B 0 (F , T ).

Let F be an anti-factorial list of periodic forbidden words with period T . We associate with F the finite deterministic automaton D(F ) described below. A finite word is accepted by this automaton if it is the label of a path from an initial state to a final one. As shown in Proposition 4, D(F ) accepts the set B 0 (F , T ) of finite blocks of X {F ,T } appearing in phase 0. An essential presentation of the PFT shift X {F ,T } is obtained from D(F ) by removing the states that have no outgoing edges or no incoming edges.

The automaton D(F ) is defined by the tuple (Q, A, i, F, δ) as follows:

• the set Q of states is 0≤k≤T -1 Q k , where Q k = {(w, k) | w is a prefix of a word in F (k) }, • A is the current alphabet,
• the initial state i corresponds to the empty word (ǫ, 0),

• the set F of final states is Q\ 0≤k≤T -1 F k , where F k = {(w, k) | w ∈ F (k) }.
The states of 0≤k≤T -1 F k are called sink states. The set of transitions T is defined as follows:

• T = {((u, k), a, (v, k + r mod T )) | (u, k) ∈ Q k \ F k , a ∈ A, and v is the longest suffix (ua)[r . . |ua| -1] of ua such that (v, k + r mod T ) ∈ Q}, (transitions ((u, k), a, (ua, k)) such that (ua, k) ∈ Q k are called
forward edges while the others are called backward edges). The partial transition function defined by transitions is denoted by δ. If w is a finite word and q a state, δ(q, w) is defined if and only if there is a path starting at q with label w. In that case, this path is unique and δ(q, w) is its ending state. Note that there is no transition going out of a sink state, but δ(q, a) is defined for any letter a and any state q that is not a sink state.

Remarks One can easily prove from the definitions that

• If q ∈ Q \ (F ∪ 0≤k≤T -1 (ε, k)
), all transitions arriving on state q have the same label.

• If q ∈ Q, there is a path from q to a sink state in the automaton.

Lemma 1: Let w be a finite word. If δ(i, w) is defined, then δ(i, w) = (v, r mod T ), where v is the longest suffix w[r . . |w| -1] of w such that (v, r mod T ) is a state of Q.

Proof: We prove the lemma by induction on the length of w. If w is the empty word, the claim is trivially satisfied. Otherwise w = ua, where a is a letter. Hence, δ(i, w) = δ(δ(i, u), a). By inductive hypothesis,

δ(i, u) = (u ′ , k mod T ), where u ′ is the longest suffix u[k . . |u| -1] of u such that (u ′ , k mod T ) is a state of Q. Since δ(i, ua) is defined, δ(i, u) is not a sink state and (δ(i, u), a, δ(i, ua)) is a transition of T. If δ(i, u) = (u ′ , k mod T ), δ(i, ua) = (v, k + r mod T ), where v is the longest suffix (u ′ a)[r . . |u ′ a| -1] of u ′ a such that (v, k + r mod T ) is a state of Q. Let v ′ be a nonempty suffix (ua)[r ′ . . |ua| -1] of ua such that (v ′ , r ′ mod T ) is a state of Q. Then v ′ = w ′ a, and w ′ is a suffix u[r ′ . . |u| -1] of u such that (w ′ , r ′ mod T ) is a state of Q.
From the inductive hypothesis, we get that w ′ is a suffix of u ′ , and thus

v ′ = w ′ a is a suffix of u ′ a. Then v is the longest suffix (ua)[r . . |ua|-1] of ua such that (v, r mod T ) is a state of Q.
Proposition 4: Let F be a finite anti-factorial list of periodic forbidden words with period T . The automaton D(F ) accepts B 0 (F , T ). It is also a presentation of X {F ,T } after removing the sink states.

Proof: We first prove that B 0 (F , T ) is included in the language accepted by D(F ). Let w be a finite block of B 0 (F , T ). If w is not accepted by D(F ), δ(i, w) is not defined. Thus there is a prefix u of w such that δ(i, u) = (v, k) is a sink state. Hence v is a suffix u[n . . |u| -1] of u, with k = n mod T , which belongs to F (k) . This implies that v ≺ n w, and w / ∈ B 0 (F , T ). Conversely, let us assume that w / ∈ B 0 (F , T ). There is an integer k with 0 ≤ k ≤ |w|, and a finite block u ∈ F (k mod T ) , such that u ≺ k w. We denote by z the word w[0 .

. k -1]. Hence zu is a prefix of w. If w is accepted by D(F ), δ(i, zu) is defined. By Lemma 1, δ(i, zu) = (v, r mod T ), where v is the longest suffix (zu)[r . . |zu| -1] of zu such that (v, r mod T ) is a state of Q. Since (u, k mod T ) is a state of Q, |v| ≥ |u|.
Since u, v are suffixes of zu, u ∈ F (k mod T ) is a suffix of v that is a prefix of a word in F (r mod T ) . The anti-factoriality of F implies that k = r mod T , and u = v. Thus δ(i, zu) is a sink state, and therefore w is not accepted by D(F ), which is a contradiction.

The above definition of the automaton D(F ) turns into the algorithm below called PERIODIC-AUTOMATON that produces it. We first consider the code of this algorithm without the lines 3.a, 3.b, 3.c and the lines 11.a, 11.b, 11.c. It builds the automaton D(F ) from a finite anti-factorial collection of finite words. With all lines included, it builds the automaton from any finite collection of finite words. The input is thus a collection of T finite sets of finite words. Each finite set of words is represented by a tree-like deterministic automaton, called a trie, defined as follows.

Let L be a finite language of finite words, a trie representing L is a finite deterministic automaton accepting L, where

• the set of states is the set of prefixes of words in L,

• the initial state is the empty word ε,

• the set of final states is F ,

• the set of transitions is {(u, a, ua) | a ∈ A}.
The size of a trie T is defined as its number of states and it is denoted by |T |.

The input of our algorithm is the set of tries 2). The output is the deterministic automaton accepting D(F ). It is denoted by (Q, A, i, T, δ). An essential representation of X {F ,T } is obtained from it by removing the states that have no outgoing edges or no incoming edges, and by setting all states both initial and final.

T k = (Q k , A, i k , F k , δ k ) that accept the finite sets F (k) , for 0 ≤ k ≤ T -1 (see Figure
The key point for the final efficiency is the use of a function f called a failure function and defined on the set Q, the union of the sets Q k of states of the tries T k , as follows. A state of the trie T k is identified with a pair (u, k), where u is a prefix of a word in

F (k) . For a state (au, k) ∈ Q, f (au, k) is δ(i k+1 mod T , u). Note that f (i k ) is undefined for any k such that 0 ≤ k ≤ T -1,
which justifies a specific treatment of the initial states in the algorithm. The failure function guarantees a good time complexity of the algorithm. The shift X {F ,T } , given in Figure 2, is presented by the deterministic automaton of Figure 3. The doubled circled states can be removed. For each state p, the value of the failure function is represented as the target of the dashed edge starting at p. States can be divided into two subsets, the set of states in phase 0 (in white) and the set of states in phase 1 (in gray). Note that all transitions go from a state in phase 0 to a state in phase 1 or conversely. Presentation of the shift X {F ,T } , where {F , T } is defined by

PERIODIC-AUTOMATON (tries

T k = (Q k , A, i k , F k , δ k ) accepting F (k) , integer T ) 1. set Q = S k Q k , F = S k F k , i = i0. 2. for each a ∈ A and each k, 0 ≤ k ≤ T -1 3.a if i k ∈ F , remove transition δ k (i k , a) in T k 3.b if δ k (i k , a) is defined and i k+1 mod T ∈ F 3.c remove transition δ k (i k , a) in T k 4. if δ k (i k , a) is defined 5. set δ(i k , a) = δ k (i k , a) 6. set f (δ(i k , a)) = i k+1 mod T 7.
F (0) = {010}, F (1) = {101} and T = 2.
Proposition 5: Let (T k ) 0≤k≤T -1 be the tries of a finite antifactorial list F of periodic forbidden words for the period T . Algorithm PERIODIC-AUTOMATON builds the deterministic automaton D(F ).

Proof: Since we assume that F is anti-factorial, we skip the lines 3 and 11 of the code of the algorithm. The automaton computed by the algorithm has a set of states Q which is the union of the set of states of the input tries. The automaton is deterministic by construction.

Let p = (u, k) be a state of Q k . We prove by induction on the length of u that: Property 1 is trivially satisfied when u is a letter. Property 2 is trivially satisfied when u is the empty word.

1) if u = ε, f (p) = (v, k + r mod T ), where v is the longest suffix u[r . . |u| -1] of u, distinct from u, such that (v, k + r mod T ) ∈ Q, 2) if a is a letter of A,
Let u be a nonempty finite word, p = (u, k) ∈ Q. Hence u = u ′ a, where a is a letter, and we denote by p ′ the state

(u ′ , k) of Q k .
By the inductive hypothesis of 1, since |u ′ | < |u|, either u ′ = ε and Property 1 is satisfied for the state p, or u ′ = ε, and

f (p ′ ) = (v ′ , k + r ′ mod T ), where v ′ is the longest suffix u ′ [r ′ . . |u ′ |-1] of u ′ , distinct from u ′ , such that (v ′ , k + r ′ mod T ) ∈ Q. By the inductive hypothesis of 2, since |v ′ | < |u ′ | < |u|, δ(f (p ′ ), a) = (w ′ , k + r ′ + s ′ mod T ), where w ′ is the longest suffix (v ′ a)[s ′ . . |v ′ a|-1] of v ′ a such that (w ′ , k + r ′ + s ′ mod T ) ∈ Q. Then f (p) = δ(f (p ′ ), a) = (w ′ , k + r ′ + s ′ mod T ). Thus, the block w ′ is a proper suffix of u ′ a = u. Let z be a proper suffix (u ′ a)[t . . |u ′ a| -1] of u ′ a such that (z, k + t mod T ) ∈ Q. Then z = z ′ a and z ′ is a suffix u ′ [t ′ . . |u ′ |-1] of u ′ distinct from u ′ , with (z ′ , k+t mod T ) ∈ Q.
This implies that z ′ is a suffix of v ′ , and that z = z ′ a is a suffix of w ′ . Then Property 1 is satisfied for the state p.

We now consider two cases to prove property 2. Let a be a letter of the alphabet. Let us assume first that there is a transition δ k (p, a). Then δ(p, a) is defined as δ k (p, a) = (ua, k) and Property 2 is satisfied. Otherwise, δ(p, a) is defined as δ(f (p), a). Since Property 1 is satisfied for the state p, f (p) is the state (v, k + r mod T ), where v is the longest suffix u

[r . . |u| -1] of u distinct from u such that (v, k + r mod T ) ∈ Q. Hence |v| < |u|. Then, by inductive hypothesis of 2, δ(f (p), a) = (x, k + r + s mod T ), where x is the longest suffix (va)[s . . |va| -1] of va such that (x, k + r + s mod T ) ∈ Q. Thus x is a suffix of ua. If y is a suffix (ua)[t . . |ua|-1] of ua such that (y, k +t mod T ) ∈ Q, then y = y ′ a and y ′ is a suffix u[t . . |u| -1] of u such that (y ′ , k + t mod T ) ∈ Q. Thus either y ′ = u or y ′ is a suffix of v.
The former case implies t = 0 and δ k (p, a) exists, which is excluded. The latter case implies that y = y ′ a is a suffix of va, and thus a suffix of x. It follows that δ(p, a) = (x, k + t mod T ), where x is the longest suffix (ua)[t . . |ua| -1] of ua such that (x, k + t mod T ) ∈ Q. Since δ(p, a) is defined as δ(f (p), a), Property 2 is satisfied for the state p.

Therefore, assuming that F is anti-factorial, it remains to check that the instructions implement the definition of D(F ).

Corollary 1: Let (T k ) 0≤k≤T -1 be the tries of a finite list F of periodic forbidden words for the period T . Algorithm PERIODIC-AUTOMATON builds a deterministic automaton accepting B 0 (F , T ). It is also a presentation of X {F ,T } after removing the sink states.

Proof: Now F is no longer anti-factorial. We keep the lines 3 and 11 of the code of the algorithm. The algorithm detects in lines 3.a, 3.b, 3.c and 11.a, 11.b, 11.c, a violation of the anti-factorial property of the collection F . Moreover, when F is not anti-factorial, it builds a new anti-factorial collection F ′ with B 0 (F , T ) = B 0 (F ′ , T ), by eliminating the words w in a set F (i) that have strict factors u ≺ j w in F (i+j mod T ) .

Proposition 6: If transition functions are implemented by transition matrices, algorithm PERIODIC-AUTOMATON runs in time

O(( k |Q k |) × |A|) on input T k = (Q k , A, i k , F k , δ k ), for 0 ≤ k ≤ T -1.
Proof:

If

IV. PRESENTATION OF FINITE-MEMORY SYSTEMS WITH UNCONSTRAINED POSITIONS

In this section, we use results from Sections II and III to derive an algorithm for constructing presentation of a finitememory system with unconstrained positions from a finite list of forbidden words characterizing the constraint. This construction is an alternative to the construction given in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF].

Let S be a finite-memory system (or finite type shift), T a period and U a set of unconstrained positions. Let F be a set of forbidden blocks such that S = X F . We know from Proposition 1 that the shift S σ U,T is a periodic-finitetype system defined by the collection G as follows. For k ∈ {0, . . . , T -1},

• if k ∈ U , G (k) is the (U -k)-closure of F plus the word 0, • if k / ∈ U , G (k) is the (U -k)-closure of F .
We assume that the input data of our construction are the period T and the trie T accepting a prefix-free set of forbidden blocks F of S. The construction of a presentation of S σ U,T is composed of two steps. In the first step, we build

T tries T k , 0 ≤ k ≤ T -1, accepting finite sets G (k) such that X {G,T } = S σ U,T .
In the second step, we compute a presentation of S σ U,T from the tries T k accepting G (k) . Algorithm PERIODIC-AUTOMATON of Section III performs this second step.

We describe the first step for a two-letter alphabet A = {0, 1}, but the results carry over easily to larger alphabets. In order to reduce the complexity of the construction, we slightly change the sets G (k) defined in Proposition 1 to avoid the generation of all U -flips of words in F .

If L is a set of finite words, we call prefix part of L the subset L -LA + of L, where A + is the set of nonempty words over A. Hence, the prefix part of L is obtained from L by removing the words that have a strict prefix in L itself.

If k / ∈ U , we define G (k) as the set of words obtained by setting all symbols at positions i, with i + k mod T ∈ U , to 1 in the words of F , and by keeping the prefix part of this set. If k ∈ U , G (k) is obtained by adding the word 0 to the above defined set, and by keeping again only its prefix part. It is easy to verify that S σ U,T = X {G,T } . The result is a collection of prefix-free sets but it may not be an anti-factorial collection.

Example 2 The RLL (2,7)-constraint is defined by the set of forbidden blocks F = {11, 101, 00000000}. For T = 3 and U = {1} we have to construct three sets G (k) , for k = 0, 1 and 2.

First, for every word of F , we flip the symbols 0 in positions i such that i + k mod T ∈ U . Hence, for k = 0, we get the words {11, 111, 01001001}, for k = 1 the words {11, 101, 10010010}, and for k = 2 the words {11, 101, 00100100}. The sets G (k) are obtained by taking the prefix part of the sets above, and by adding the word 0 to those G (k) such that k mod T ∈ U . We obtain

G (0) = {11, 01001001}, G (1) = {0, 11, 101, 10010010}, G (2) = {11, 101, 00100100}.
Example 3 The constrained system MTR(3) is defined by the set of forbidden blocks F = {1111}. For T = 3, U = {1}, we obtain

G (0) = {1111}, G (1) = {0, 1111}, G (2) = {1111}.
larger than the size of the input trie.

The second step of the construction uses Algorithm PERIODIC-AUTOMATON of Section III for computing a presentation of S σ U,T from tries T k accepting sets G (k) such that X {G,T } = S σ U,T . The output is an automaton A = (Q, A, i, Q \ F, δ) accepting S U,T . If the sink states (i.e. states of F ) are removed, one gets a presentation of the shift S σ U,T . We now evaluate the overall time-complexity of the process and compare it with the time-complexity of the construction given in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF]. Algorithm PERIODIC-AUTOMATON runs on tries The construction of [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF] enables the computation of a presentation of S σ U,T from a presentation of finite-state constrained system S in an exponential amount of time in general, and in quadratic time with a particular condition, called the gap condition (see [3, pp. 875]). Although our algorithm is polynomial and that given in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF] is exponential, the two algorithms compute similar presentations. But the input data are different. In particular, the minimal set of forbidden words of a finitememory system can be computed in quadratic-time (see [START_REF] Béal | Computing forbidden words of regular languages[END_REF]) from a deterministic presentation of the system when this presentation has a unique initial state. If the system is given by a deterministic presentation where all states are initial, with Q states and memory M , it can take in the worst case O(|A| M ) amount of time to compute a deterministic presentation that has a unique initial state. Thus the complexities of the two algorithms cannot be compared directly and one can choose one or the other depending on the way the constraint is defined. Some constraints may be naturally defined by a list of forbidden blocks. For instance, an MTR constraint is defined by a single forbidden block. The RLL (d, k)-constraint is defined by d forbidden blocks of length at most d + 1 and one block of length k + 1. With (d, k) = (2, 7) one gets the forbidden blocks {11, 101, 00000000}. A trie accepting a finite set is built in time linear in the sum of the lengths of the words of the set. In the particular case of the set of forbidden blocks of the (d, k)-constraint, the trie is built in time linear in d + k, i.e. since d ≤ k, in time O(k) from the inputs d and k. Moreover the trie has a size that is also O(k). Indeed, the trie has the particular linear structure described in Figure 4. It follows that Algorithm PERIODIC-AUTOMATON runs in time O(k) on this input trie. Indeed, in the analysis of the complexity in the proof of Proposition 7, s = O(|Q|) = O(k). Thus our algorithm works linearly on the MTR constraints, and on the RLL constraints. An efficient algorithm for the MTR constraints is also given in [START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF]. Figure 5 displays an example for the constraint MTR(3). The presentation can be minimized with standard methods [9]. It leads to the minimal presentation displayed in Figure 6.

T k in time O(( k |T k |) × |A|). Since |T k | ≤ |T |, it is O(T × |T |×|A|).
A condition similar to the gap condition of [3, pp. 875] can be stated as follows. We assume that there is at most one unconstrained position in {0, . . . , M -1}, where M is the

V. PERIODIC FORBIDDEN WORDS OF A SINGLE FINITE

WORD

Repetitions, and especially consecutive repetitions, play an important role in the analysis of molecular biology sequences. Some of them are even related to known deseases. From this point of view it is interesting to consider periodic forbidden words according to a single word. This may be used to discover combinatorial properties of the sequence and identify subsequence motifs either in coding regions and in "junk DNA", and then to derive statistical features on them.

In this section, we study the problem of computing the minimal periodic forbidden words of a given finite word. The problem of computing the minimal (non periodic) forbidden words of a single word has been solved in linear time in [7], see also [10, section 6.5 pp. 212]. We extend here the algorithm presented in [7] to the periodic case. The set of minimal forbidden words in a phase k of a word y, with 0 ≤ k ≤ T -1, is the set of finite blocks w that never appear at a position k mod T of y, and such that there is no strict factor w ′ of w with w ′ ≺ i w appearing at a position k + i mod T of y. In the sequel, we fix a positive integer T as period. If y is a finite word we denote by Suff (k) (y), for 0 ≤ k ≤ T -1, the set of suffixes of y beginning at a position of y equal to k modulo T . Thus,

Suff (k) (y) = {y[i . . |y| -1] | i = k mod T }.
We denote by Fact (k) (y) the set of prefixes of Suff (k) (y), that is, the set of factors of y that occur in y at positions k modulo T . In this section, we also denote by F (k) (y) the set of finite blocks that are not factors of y at a position k modulo T . Thus

F (k) (y) = A * -Fact (k) (y).
The collection of minimal periodic forbidden words of y for a period T is defined as the finite collection of sets MF (k) (y), with 0 ≤ k ≤ T -1, where

MF (k) (y) = F (k) (y) -F (k) (y)A + -(A T ) + F (k) (y)A * - T -1 i=1 (A T ) * A i F (k+i mod T ) (y)A * .
Thus, the above collection MF (k) (y) is periodic and antifactorial. It is minimal in the following sense: if u ∈ F (k) (y), then u has a factor at some position i that belongs to MF (k+i mod T ) (y), and any other collection of finite sets of blocks G (k) satisfying this condition verifies MF (k) (y) ⊆ G (k) . Although this notion of minimality refers to a finite word y, it is similar to the notion of periodic first offenders defined in [5] for constrained systems.

We now give a simpler expression of the set F (k) (y) used to derive the next algorithm.

Proposition 8: The set MF (k) (y) of minimal periodic forbidden words of y for a period T satisfies

MF (k) (y) = (A Fact (k+1 mod T ) (y)) ∩ (Fact (k) (y)A) ∩ (A * -Fact (k) (y)).
(1)

Proof: Let u be a block of (A Fact (k+1 mod T ) (y)) ∩ (Fact (k) (y)A) ∩ (A * -Fact (k) (y)). Then u ∈ F (k) (y). Since u ∈ Fact (k) (y)A, then u / ∈ F (k) (y)A + . Since u ∈ A Fact (k+1 mod T ) (y), then u ∈ A i Fact (k+i mod T ) (y) for 1 ≤ i ≤ |u|. Hence u / ∈ (A T ) + F (k) (y)A * , and u does not belong to

T -1 i=1 (A T ) * A i F (k+i mod T ) (y)A * either.
Conversely, let u be a block of MF (k) (y). Then u ∈ F (k) (y). If u / ∈ Fact (k) (y)A, then u = va, with a ∈ A, and v ∈ F (k) (y). Hence u ∈ Fact (k) (y)A. Let us now assume that u / ∈ A Fact (k+1 mod T ) (y). Then u = av, with a ∈ A and v ∈ F (k+1 mod T ) (y). Then v has a factor at position i belonging to MF (k+1+i mod T ) (y). This contradicts the fact that u does not belong to

T -1 i=1 (A T ) * A i F (k+i mod T ) (y)A * ∪ (A T ) + F (k) (y)A * .
Hence MF (k) (y) satisfies (1). We now describe an algorithm for computing the collection MF (k) (y). The design of the algorithm is based on (1). A preliminary step of the algorithm consists in computing, for any 0 ≤ k ≤ T -1, a minimal deterministic automaton accepting Suff (k) (y). This operation can be performed in time

O(T × |y| × log |A|).
First, the computation of a minimal deterministic automaton accepting Suff (k) (y) is reduced to the computation of a minimal deterministic automaton accepting Suff (0) (y[k . . |y| -1]). Hence, we will assume, without loss of generality, that k = 0. The computation of a minimal deterministic automaton accepting Suff (0) (y) is an extension of the known computation of the minimal automaton of the suffixes of a word, also called the directed acyclic word graph (DAWG) of a word (see for instance [START_REF] Blumer | Linear size finite automata for the set of all subwords of a word : an outline of results[END_REF], [START_REF]Building a complete inverted file for a set of text files in linear time[END_REF] or [10, section 5.4 pp. 179-192]).

The states of this automaton are the equivalence classes of the syntactic congruence associated with the language Suff (0) (y) defined as follows: if u ∈ Fact(y), we denote by F y (u) the future of u relative to Suff (0) (y). Thus F y (u) = {v | uv ∈ Suff (0) (y)}. Note that F y (y) is reduced to the empty word, and that F y (u) is the empty set if u / ∈ Fact (0) (y). The words u and v are equivalent if and only F y (u) = F y (v).

Moreover, the automaton has a transition labelled by a from the class of a word u to the class of ua. If u ∈ Fact(y), we define its image s(u) by the suffix function s as the longest suffix v of u in Suff (0) (u) such that F y (v) = F y (u). In this case, F y (u) ⊆ F y (v).

It can be shown that if p is a state representing a class of congruent factors of y, and if u belongs to this class, all s(u) belong to the same class of the congruence. Thus, one can define the suffix link of the state p, denoted by s(p), as the class of s(u).

In the description below, deterministic automata are denoted by (Q, A, i, F, δ), where Q is the set of states, A the alphabet, i the initial state, δ the partial transition function, and F the set of final states. A transition labelled by a from p to q is also denoted by the edge (p, a, q). The algorithm generating the minimal automaton accepting Suff (0) (y) is described in Procedure PERIODIC-SUFFIX-AUTOMATON. It is an incremental algorithm that computes successively a minimal automaton accepting Suff (0) (y[0 . . i]), for i going from 0 to |y| -1. This procedure calls procedures EXTENSION and SPLIT. Procedure EXTENSION performs the transformations needed to get a minimal automaton accepting Suff (0) (y[0 . . i]) from a minimal automaton accepting Suff (0) (y[0 . . i-1]). Some dummy states are added during the construction. The suffix link is not defined for these dummy states. The transitions belonging to some longest path from the initial state to some other state are called solid while the others are called weak. If p is a state of the automaton, the sequence of states p, s(p), s(s(p)), . . . is finite and ends with a dummy state. This sequence is called the suffix path of p. If p is the class of y, the non-dummy states of its suffix path are the final states of the automaton. set s(q) = r + 1 9. else 10. let s = δ(r, a) 11.

if the transition (r, a, s) is solid 12. set s(q) = s 13. else 14.

set s(q) = SPLIT(r, a, s) 15. return q SPLIT (state p, letter a, state q)

1. create a new state q ′ 2. for each transition (q, a, r) create a weak transition (q ′ , a, r) 3. change the (weak) transition (p, a, q) into a solid transition (p, a, q ′ ) 4. set s(q ′ ) = s(q) 5. set s(q) = q ′ 6. let t = s(p) 7. while t ≥ 0 and the transition (t, a, q) is weak do 8. change (t, a, q) into (t, a, q ′ ) 9.

set t = s(t) 10. return q ′ Proposition 9: Algorithm PERIODIC-SUFFIX-AUTOMATON computes the minimal deterministic automaton accepting Suff (0) (y) for a given period T .

Proof: The proof is an extension to the periodic case of the correctness proof of the computation of the minimal deterministic automaton accepting the set of all suffixes of y (see [10, section 5.4 pp. 179-192]). We omit the proof but we mention below the main differences needed to take the period into account. If p is a state such that l(p) < T , the suffix link s(p) is the dummy state -T + l(p). Let us assume that we are at step i, lines 5-6 of Procedure PERIODIC-SUFFIX-AUTOMATON(y, T ). Let us denote y[0 . . i -1] by w. Let r be the state obtained at the end of the loop in lines 4-6 of Procedure EXTENSION(p, a). If r is a dummy state, for any word u in Suff (0) (w), either F w (u) = F w (w) = {ε} or ua / ∈ Fact (0) (w).

Proposition 10: The size of the minimal automaton accepting Suff (0) (y) for a given period T is linear in the size of y. Algorithm PERIODIC-SUFFIX-AUTOMATON runs in time linear in the size of y.

Proof: The proof is similar to the proof in the aperiodic case [10, section 5.4 pp. 192].

Making all states final in the minimal deterministic automaton accepting Suff (k) (y) gives a deterministic automaton accepting Fact (k) (y). Note that this new automaton may not be the minimal one. An example is given in Figure 7.

We now describe the second step of the algorithm. We denote by A k = (Q k , A, i k , Q k , δ k ) a deterministic automaton accepting Fact (k) (y), that is the set of blocks, factors of y, beginning at a position equal to k modulo T . From the automata A k , the algorithm outputs the tries T k accepting the sets MF (k) (y). An example of this computation is described in Figure 8.

PERIODIC-MF-TRIES ( factor automata

A k = (Q k , A, i k , F k , δ k )) 0≤k≤T -1 , integer T ) 1. for each a ∈ A 2.
if δ k (i k , a) defined Proposition 11: Algorithm PERIODIC-MF-TRIES computes from the automata A k accepting Fact (k) (y) the set of tries accepting the minimal periodic forbidden words of y.

Proof: Again, the proof is an extension of the correctness proof of the computation of the minimal forbidden words of a word from the factor automaton of y (see [10, section 6.5 pp. 182] or [7]).

Proposition 12: Algorithm PERIODIC-SUFFIX-AUTOMATON followed by algorithm PERIODIC-MF-TRIES runs in time O(|y| × T × log |A|).

Proof: The complexity is straightforward. . Output tries T 0 and T 1 of Algorithm PERIODIC-MF-TRIES for the input tries A 0 and A 1 described in Figure 7. The sink states are double circled. The tries T 0 and T 1 accept MF (0) (y) = {c, aa, bb} and MF (1) (y) = {c, ba, aa, aba} respectively.

Fig. 1 .

 1 Fig.1. An automaton presenting a periodic-finite-type shift X. The shift X admits the following list of periodic forbidden words, for T = 2, F (0) = {1}, F(1) = ∅.

else 8 .Fig. 2 .

 82 Fig.[START_REF] Wijngaarden | Maximum run-length limited codes with error control properties[END_REF]. Example of the two input tries for the collection F defined by F (0) = {010}, F(1) = {101} and T = 2. Final states are doubled circled.

  Fig.[START_REF] Campello De Souza | Constrained systems with unconstrained positions[END_REF].Presentation of the shift X {F ,T } , where {F , T } is defined by F (0) = {010}, F(1) = {101} and T = 2.

  and δ(p, a) is defined, δ(p, a) = (w, k + s mod T ), where w is the longest suffix (ua)[s . . |ua|-1] of ua such that (w, k+s mod T ) ∈ Q.

  transition functions δ k and δ are implemented by transition matrices, access to or definition of δ k (p, a) or δ(p, a) (p state, a ∈ A) are realized in constant amount of time. The result follows immediately.

  Then the overall time-complexity for the input data T and a trie T accepting a prefix-free set of forbidden blocks of S, is O(T × |A| × |T | log |T |). It becomes linear for linear tries. The evaluation of the space complexity is similar and gives O(T × |A| × |T |).

Fig. 4 .Fig. 5 .

 45 Fig. 4. The trie of the RLL (d, k)-constraint.

Fig. 6 .

 6 Fig. 6. The Shannon cover of S σ U,T for S = MTR(3), T = 3, U = {1}. It is the minimal presentation of that of Figure 5.

  3. set δ(i k , a) = δ k (i k , a) 4. set f (δ(i k , a)) = i k+1 mod T 5. else 6. set δ(i k , a) = new sink 7. for each state p ∈ Q k in width-first search from ∪ k {i k } and each a ∈ A 8. if δ k (p,a) undefined and δ k+1 mod T (f (p), a) defined 9. set δ(p, a) = new sink 10.else if δ k (p, a) = q and q not already reached11. set δ(p, a) = q 12. set f (δ(p, a)) = δ(f (p), a) 13. return (T k = (Q k , A, i k , {sinks}, δ)) 0≤k≤T -1 ;

Fig. 7 .

 7 Fig.7.Deterministic automata A 0 and A 1 accepting Fact (0) (y) and Fact(1) (y) respectively, with the period T = 2 and y = abbab. The suffix links are represented by dashed edges.

Fig. 8

 8 Fig.8. Output tries T 0 and T 1 of Algorithm PERIODIC-MF-TRIES for the input tries A 0 and A 1 described in Figure7. The sink states are double circled. The tries T 0 and T 1 accept MF (0) (y) = {c, aa, bb} and MF(1) (y) = {c, ba, aa, aba} respectively.

  PERIODIC-SUFFIX-AUTOMATON (word y, period T ) 1. create T dummy states -1, -2, . . .

		-T
	2. create an initial state 0
	3. set s(0) = -T
	4. let p = 0
	5. for i from 0 to |y| -1 do
	6.	p = EXTENSION(p, yi)
	7. let f = p
	8. while f ≥ 0 do
	9.	set f final
	10.	set f = s(f )
	11. return automaton (Q, A, 0, E, {final})
	EXTENSION (state p, letter a)
	1. create a new state q
	2. create a new solid transition (p, a, q)
	3. let r = s(p)
	4. while r ≥ 0 and there is no transition a going out of r do
	5.	create a weak transition (r, a, q)
	6.	set r = s(r)
	7. if r < 0
	8.

We will use the following operation on tries accepting prefixfree sets of words. If T and T ′ are two tries accepting prefix-free sets of words L and L ′ respectively, we denote by PREFIX-FREE-UNION(T , T ′ ) a procedure that computes a trie accepting the prefix part of L ∪ L ′ .

Proposition 7: Algorithm PERIODIC-TRIES runs in time O(|Q| log |Q| × T × |A|) on the input trie T = (Q, A, i, F, δ) and the input period T .

Proof:

If p is a state of the trie T , we denote by l(p) the (eventually empty) left subtrie of p, i.e. the subtrie rooted by δ(p, 0). Similarly, we denote by r(p) the (eventually empty) right subtrie of p. Thus Algorithm PERIODIC-TRIES(T = (Q, A, i, F, δ)) runs in time O(T × |A| × p∈Q min(|l(p)|, |r(p)|). We now evaluate the sum s = p∈Q min(|l(p)|, |r(p)|). We say that a subtrie of a state p is small if it has the smallest size among the two subtries children of p. Then each state belongs to at most log 2 |Q| small subtries. It follows that s ≤ |Q| log 2 |Q|.

We mention that other simplifications may be added in the procedure PERIODIC-TRIES. For instance, if we are interested in computing bi-infinite words or right-infinite words, any two words u0 and u1 accepted by a trie may be removed and replaced by u. Indeed, in the case of infinite words, if u0 and u1 are forbidden in a position i, then u is also forbidden. Nevertheless, this simplification does not reduce the overall asymptotic complexity of the process.

Note that, if one considers |A| and T as constants, the |Q| log |Q| time-complexity obtained in Proposition 7 becomes linear in |Q| when the input trie T is linear, i.e. accepts a single word. Note also that each output periodic trie has a size not


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

Lucian Ilie
email: ilie@csd.uwo.ca

Maximal repetitions in strings ⋆

Keywords: combinatorics on words, repetitions in strings, runs, maximal repetitions, maximal periodicities, sum of exponents MSC: 68R15, 68W40

come

Introduction

Repetitions in strings constitute one of the most fundamental areas of string combinatorics with very important applications to text algorithms, data compression, or analysis of biological sequences. They have been study already in the papers of Axel Thue [START_REF] Thue | Über unendliche Zeichenreihen, Kra. Vidensk[END_REF], considered as having founded stringology. While Thue was interested in finding long sequences with few repetitions, one of the most important problems from the algorithmic point of view was finding all repetitions fast. A major obstacle for a linear-time algorithm was finding a way to encode all repetitions in linear space. The problem was studied first by Crochemore [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF] where maximal (non-extendable) integer powers were introduced and an (optimal) O(n log n) algorithm for finding them all was given. Moreover, the bound was shown to be optimal as it is reached by the Fibonacci strings.

The next step was to consider occurrences of fractional repetitions, of right-maximal (non-extendable to the right) repetitions by Apostolico and Preparata in [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF] and then of maximal (non-extendable both ways, called runs for the rest of the paper) repetitions by Main [START_REF] Main | Detecting lefmost maximal periodicities[END_REF] who gave a linear-time algorithm for finding all leftmost occurrences of runs.

Iliopoulos et al. [START_REF] Iliopoulos | A characterization of the squares in a Fibonacci string[END_REF] showed that for Fibonacci strings the number of maximal repetitions is linear. Even if their result applies to a particular class of strings, it is important since the Fibonacci strings were known to contain many repetitions. The breakthrough came in the paper of Kolpakov and Kucherov [START_REF] Kolpakov | On maximal repetitions in words[END_REF], where it was finally proved that encoding all occurrences of repetitions into runs was the right way to obtain a linear-sized output. They modified Main's algorithm to compute all runs in linear time; see [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF]. For more details on various algorithms computing repetitions, see Chapter 8 of [START_REF] Lothaire | Applied Combinatorics on Words[END_REF].

Kolpakov and Kucherov [START_REF] Kolpakov | On maximal repetitions in words[END_REF] showed that the number of runs in a string of length n is at most cn but their proof could not provide any value for the constant c. Another breakthrough came very recently, when Rytter [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF] proved that c ≤ 5. Puglisi et al. [START_REF] Puglisi | How many runs can a string contain?[END_REF] improved Rytter's analysis to bring the constant down to 3.48 and then Rytter [START_REF] Rytter | The number of runs in a string[END_REF] produced his own version of the improved analysis with a constant factor of 3.44. The fact that the two bounds are so close may show that the ideas in Rytter's initial paper have been well squeezed.

Based on the results in Table 1, Kolpakov and Kucherov [START_REF] Kolpakov | On maximal repetitions in words[END_REF] conjectured that c = 1 for binary alphabets. A stronger conjecture is proposed in [START_REF] Franek | The maximum number of runs in a string[END_REF] where a family of strings is given with the number of runs equal to 3 2φ = 0.927 . . . (φ is the golden ratio), thus proving c ≥ 0.927 . . .. The authors of [START_REF] Franek | The maximum number of runs in a string[END_REF] conjectured that this bound is optimal. Some reasons which might indicate that the optimal bound may be less than n are discussed in Section 7.

Table 1 Maximum number of runs in binary strings of length n, 5 ≤ n ≤ 31 (from [START_REF] Kolpakov | On maximal repetitions in words[END_REF]). The proof of [START_REF] Kolpakov | On maximal repetitions in words[END_REF] is extremely long and complex and the one of [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF] is still very intricate. (The two improvements in [START_REF] Puglisi | How many runs can a string contain?[END_REF] and [START_REF] Rytter | The number of runs in a string[END_REF] only make a more careful analysis of the ideas of [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF].) A simple proof for the linearity is given by the authors in [START_REF] Crochemore | A simple proof that the number of runs in a word is linear[END_REF] where an improvement of the notion of neighbors of [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF] is introduced.

It is interesting to notice that the number of runs having the same starting point is logarithmic, due to the three-square lemma of [START_REF] Crochemore | Squares, cubes, and time-space efficient string searching[END_REF], that is, they are not uniformly distributed, which makes proving linearity hard. The situation is even worse for centers (beginning of the second period of the run -see next section for details) where linearly many runs can share the same center. However, while Rytter [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF] counted runs by their beginnings, we count them by centers and obtain much better results. A more detailed comparison of the two approaches is included in Section 3.

In this paper we improve significantly the previous results by proving the bound 1.6n on the number of runs in a string of length n. This bound can be lowered a bit by extra effort for the runs with short periods, but we show also how it could be improved by computer verification down to 1.18n or even further. Notice that the bound on the number of runs has an important direct impact on the running time of all algorithms computing all repetitions since it says how many runs we expect the algorithm to output. It is important as well from mathematical point of view, that is, to find the best upper bound on the number of runs, and from algorithm-design point of view, as it may lead to simpler algorithms for finding all repetitions (the algorithm of [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF] uses relatively complicated data structures such as suffix trees). While the conjecture may be very difficult to solve, we believe that our work provides a good approximation for all practical purposes.

The approach in [START_REF] Crochemore | A simple proof that the number of runs in a word is linear[END_REF] is used also to give a simple proof for the stronger result concerning the linearity of the sum of exponents. This result has been proved by Kolpakov and Kucherov [START_REF] Kolpakov | On the sum of exponents of maximal repetitions in a word[END_REF]. (It follows also from Rytter's construction in [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF].) It has applications to the analysis of various algorithms, such as computing branching tandem repeats: the linearity of the sum of exponents solves a conjecture of [START_REF] Stoye | Simple and flexible detection of contiguous repeats using a suffix tree[END_REF] concerning the linearity of the number of maximal tandem repeats and implies that all can be found in linear time.

For other applications we refer to [START_REF] Kolpakov | On the sum of exponents of maximal repetitions in a word[END_REF].

But the proof of [START_REF] Kolpakov | On the sum of exponents of maximal repetitions in a word[END_REF] is very complex and could not provide a constant. A bound can be derived from the proof of Rytter [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF] but he mentioned only that the bound that he obtains is "unsatisfactory." It seems to be 25n. The improved analysis in [START_REF] Rytter | The number of runs in a string[END_REF] does not mention the sum of exponents at all. We provide here the first explicit bound, which is 5.6n. As with the other bound, extra effort for the runs with short periods can lower the bound, but we show how it could be improved by computer verification down to 2.9n or further. As mentioned in [START_REF] Kolpakov | On the sum of exponents of maximal repetitions in a word[END_REF], computations seem to indicate a 2n bound.

The paper is organized as follows. In the next section we give the basic definitions needed in the paper. The new bound is given in the following section which contains also a comparison between our approach and the one of Rytter [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF][START_REF] Rytter | The number of runs in a string[END_REF]. Our approach is more accurate for both long and short periods. The division into two subsets according to period length is natural because, as explained in Section 3, no approach seems to work well for both. For long ones, Rytter [START_REF] Rytter | The number of runs in a string[END_REF] proves the bound 0.67n for runs with periods 87 or higher. For comparison sake, we could easily deduce the corresponding bound using our approach: it is 0.06897n, that is, roughly ten times better. The analyses needed for the new bound are presented in Section 4, for runs with arbitrarily long periods, and Section 5, for runs with periods 9 or less. The sum of exponents in discussed in Section 6. Some comments on both bounds, as well as ways to improve them further by computer verification are included in Section 7. We conclude with a discussion on several other related problems.

Definitions

Let A be an alphabet and A * the set of all finite strings over A. We denote by |w| the length of a string w, its ith letter by w[i] and the factor w

[i]w[i + 1] . . . w[j] by w[i . . j].
We say that w has period p iff w[i] = w[i + p], for all i, 1 ≤ i ≤ |w|p. The shortest period of w is called the period of w. The ratio between the length and the period of w is called the exponent of w.

For a positive integer n, the nth power of w is defined inductively by w 1 = w, w n = w n-1 w. A string is primitive if it cannot be written as a proper (two or more) integer power of another string. Any string can be uniquely written as an integer power of a primitive string, called its primitive root. The following well-known synchronization property will be useful for us: if w is primitive, then w appears as a factor of ww only as a prefix and as a suffix (not in-between). Another property we use is Fine and Wilf 's periodicity lemma: If w has periods p and q and |w| ≥ p + q, then w has also period gcd(p, q). (This is a bit weaker than the original lemma which works as soon as |w| ≥ p + qgcd(p, q), but it is good enough for our purpose.) We refer the reader to [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF][START_REF] Lothaire | Applied Combinatorics on Words[END_REF] for further information on all concepts used here.

For a string w, a run3 (or maximal repetition) is an interval [i .

. j] such that both (i) the factor w[i . . j] has its shortest period at most j-i+1 2 and (ii) w[i -1 . . j] and w[i . . j + 1], if defined, have a strictly higher shortest period. As an example, consider w = abbababbaba; [3 . . 7] is a run with period 2 and exponent 2.5; we have w[3 . . 7] = babab = (ba) By definition, a run is a maximal occurrence of a repetition of exponent at least two. Therefore, it starts with a square and continues with the same period. But the square is the only part of the run we can count on. Therefore, for a run starting at i and having period |x| = p, we shall call w[i . . i + 2p -1] = x 2 the square of the run. Notice that x is primitive and the square of a run is not left-extendable (with the same period) but may be extendable to the right. The center of the run is the position c = i + p. We shall denote the beginning of the run by i x = i, the end of its square by j x = i x + 2p -1, and its center by c x = c.

The bound

The idea is to partition the runs by grouping together those having close centers and similar periods and then prove that we have only one on the average in each group. For any δ > 0, we say that two runs having squares x 2 and y 2 are δ-close if both (i) |c x -c y | ≤ δ and (ii) 2δ ≤ |x|, |y| ≤ 3δ. Abusing the language, we shall sometimes say that the squares, instead of the runs, are δ-close. Another notion that we shall use frequently is that of runs with the periods between 2δ and 3δ; we shall call those δ-runs.

We prove (Section 4) that the number of runs is highest when any interval of length δ contains only one center of a δ-run. That means that the number of δ-runs in a string of length n is at most n δ . We could then sum up for values of δ which would cover all possible periods but we make one further improvement. Since any bound for arbitrarily long runs performs poorly on runs with short periods, we bound separately the number of runs with short periods; precisely we prove that there are at most n runs with period at most 9 in any string of length n (Section 5).

Summing up the above for all values δ i = 10 2 3 2

i , i ≥ 0, to cover all periods greater than 9, we obtain the following upper bound for the number of runs in a string of length n:

n + ∞ i=0 n δ i = n + 2 10 ∞ i=0 2 3 i n = 1.6n . (1)
Our main result is Theorem 1 The number of runs in a string of length n is less than 1.6n.

Our approach differs from the one of Rytter [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF] in several respects. First, our notion of δ-closeness is different from his notion of neighbors. We consider the case when the centers of the runs are close to each other as opposed to beginnings as this gives us a better overlap between the runs. Thus we can choose a better interval length for the periods. Second, we make a combinatorially finer analysis of the close runs which enables us to count all runs together; [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF] splits them into weekly and highly periodic. Doing so, the proof becomes conceptually simpler. For runs with long periods we can say that our approach is about ten times better than Rytter's. He explicitly states that the number of runs with periods larger than 87 is at most 0.67n. With our approach, this number is about ten times smaller:

2 87 ∞ i=0 2 3 i n ≤ 0.06897n .
Third, our approach for runs with short periods is different from the one of [START_REF] Rytter | The number of runs in a string: improved analysis of the linear upper bound[END_REF]. We essentially verify that the conjecture is true up to a certain threshold for the periods of the runs. Due to the complexity of the analysis, we restricted this threshold to 9 but it can be checked automatically for higher thresholds, every time improving the bound. More on this is in Section 7.

Runs with close centers

In this section we show that, for a given δ, each interval of positions of length δ contains at most 1 center of a δ-run on the average. The result is used for runs having a period greater than 9 in the sum [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF].

We investigate what happens when two (or, sometimes, three) runs in a string w are δ-close. Denote their squares by x 2 , y 2 , z 2 , their root lengths by |x| = p, |y| = q, |z| = r, and assume p ≤ q ≤ r.

We discuss below all ways in which occurrences of x 2 and y 2 can be positioned relative to each other and see that long factors of both runs have short periods. When we have only two δ-close runs, synchronization properties show that the next (to the right) interval of length δ (as counted in (1)) does not contain any center of a δ-run.

When we have three δ-close runs, z 2 has to synchronize the short periods mentioned above, which restricts the beginning of z 2 to only one choice as otherwise some run would be left extendable (which is not possible). Stronger periodicity properties are implied by the existence of the third run and we can find an interval of length at least 4δ which contains no other center of δ-runs. Such an interval covers at least three intervals of length δ no matter how the decomposition of [1 . . n] into such intervals is done. Thus, less runs than in (1) are obtained.

It is also possible to have arbitrarily many δ-close runs, that is, when they all have the same center; case (i). A similar global counting approach is performed in this case. The existence of such runs implies strong periodicity properties of a factor of w and we exhibit a long interval without any center of runs with certain periods. In total, less runs than in (1) are obtained.

There can exist several δ-close runs such that some of them only share the same center. Therefore, we shall discuss the case of many runs having the same center first. It helps solving some situations in the other cases.

(i) c x = c y . First, both x and y have the same small period ℓ = qp; see Fig. 1. If we denote c = c y then we have h runs

x αj j , 2 ≤ α j ∈ Q, for 1 ≤ j ≤ h, having period |x j | = (j -1)ℓ + ℓ ′ and beginning at i xj = c -((j -1)ℓ + ℓ ′ ). If we set x j = u j-1 u ′ , with |u| = ℓ, |u ′ | = ℓ ′ ,
then the last letters of u and u ′ are different, as otherwise x would be left-extendable. As an example, take w = (ab) 6 aa(ba) 6 , where c = 14, h = 7, ℓ = 2, ℓ ′ = 1, u = ab, and u ′ = a. We show that for h ≥ 6 we have less runs than in [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF]. Notice that only for h ≥ 7 we can have three of the x αj j s mutually δ-close. Therefore, we may assume for the other cases ((ii)-(v)) that there are no three δ-close runs with the same center.

There exists δ i0 such that ℓ 2 ≤ δ i0 ≤ 3ℓ 4 , that is, this δ i0 is considered in [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF]. The periods corresponding to δ i0 are between ℓ and 9 4 ℓ. We claim that there is no run in w with period between ℓ and 9 4 ℓ and center inside the interval J = [c + ℓ + 1 . . c + (h -2)ℓ + ℓ ′ ]. Indeed, assume there is a run with the initial square t 2 , c t ∈ J. If i t ≥ c, then the prefixes of length ℓ of the first and second occurrences of t, respectively, must synchronize. If i t > c, then t 2 is left-extendable, a contradiction. If i t = c, then ℓ divides |t| and hence t is not primitive, a contradiction. If i t < c, then synchronization is obtained (either the prefixes or the suffixes of length ℓ of the two occurrences of t synchronize) and we get that the last letters of u and u ′ are the same, a contradiction.

Then, the length of J is larger than (h -3)ℓ which in turn is larger than (h -2)δ i0 (since 3ℓ ≥ 4δ i0 and h ≥ 6). Thus J covers at least h -3 intervals of length δ i0 that would contain, if considered in (1), h -3 runs. This is enough as we need to account, for each δ from ( 1), for the extra runs, that is, all but one. At least three δs are needed for all our h runs, so we need to account for at most h -3 runs, which we already did.

We need also mention that these h intervals of length δ i0 are not reused by a different center with multiple runs since such centers cannot be close to each other. Indeed, assume we have two centers c j with the above parameters h j , ℓ j , j = 1, 2. Then the periods satisfy ℓj 2 ≤ δ i0 ≤ 3ℓj 4 , j = 1, 2, and so ℓ j ≤ 3 2 ℓ 3-j , j = 1, 2. As soon as the longest runs with centers at c 1 and c 2 , respectively, overlap over ℓ 1 + ℓ 2 positions, we have ℓ 1 = ℓ 2 , due to Fine and Wilf's lemma. Thus, the closest positions of J 1 and J 2 cannot be closer than ℓ 1 = ℓ 2 ≥ δ i0 as otherwise some of the runs become non-primitive, a contradiction.

(ii) (i y < i x ) < c y ≤ c x < e x ≤ e y . Then x and the suffix of length c yi x + (qp) of y have period qp; see Fig. 2. (Only the periods to the left of e y are implied by x 2 and y 2 , the ones to the right of e y are obtained in the case when a third run, z 2 , exists -see below.) We may assume this period is a primitive string as otherwise we can make the same reasoning with its primitive root. It is not difficult to see that no δ-run can have its center in the interval [c y +δ . . c y +2δ] as it would be left extendable. This argument is sufficient for the case when no third δclose run exists.

If there is a third run, z 2 , then we need a stronger argument to account for the three centers in the same interval of length δ. Since z 2 is δ-close to both x 2 and y 2 , it must be that c z ∈ [c xδ . . c y + δ]. Consider the interval of length qp that ends at the leftmost possible position for c z , that is, I = [c xδ -(qp) . . c xδ -1]; see Fig. 2. The following arguments show that it is included in the first period of z 2 , that is, [i z . . c z -1], and in [i x . . c y -1]. It is clear that I ends before both c z -1 and c y -1. The other two inequalities are proved as follows. First i z = c zr ≤ c y + δq ≤ c x + pδq. Then i x = c xp ≤ c xδq + p. Subsequently, all such inequalities can be proved similarly and are left as exercises.

Thus w[I] is primitive and equal, due to z 2 , to w[I + r] which is contained in [c x . . e y ]. Therefore, the periods inside the former must synchronize with the ones in the latter. It follows, in the case

i z > i x -(q-p), that w[i z -1] = w[c z -1], that is, z 2 is left extendable, a contradiction. If i z < i x -(q -p), then w[c x -1] = w[i x -(q -p) -1] = w[i x -1], that is, x 2 is
left extendable, a contradiction. The only possibility is that i z = i x -(qp) and r equals q plus a multiple of qp. Here is an example that this is indeed possible: w = baabababaababababaab, x 2 = w[5 . . 14], y 2 = w[1 . . 14], and

z 2 = w[3 . . 20].
The existence of z 2 implies that the period of the second occurrence of y extends past e y , as seen in Fig. 2. Consider the interval J = [i z + 2(qp) . . e z -2(qp)]. The existence of a fourth δ-run with center inside J but different from c x would imply that either x 2 or z 2 is left extendable, a contradiction. (Notice that we allowed the length of two (qp)-periods at either end of J so that the hiccup of the period ending at c x does not cause any problems.) On the other hand, such a run can have c x as its center. If so, then all such runs are accounted for by case (i) since we have at least three periods at c x between 2δ and 3δ: q, q -(qp), and q -2(qp). The length of J is 2r -4(qp) ≥ 2(q + qp) -4(qp) = 2p ≥ 4δ and therefore it covers at least three intervals of length δ. In total, we have at most the number of runs as counted in (1).

(iii) (i y < i x ) < c y < c x < e y ≤ e x . This case is similar with (ii); see the top part of Fig. 3. Again, no δ-run can have its center in the interval [c y + δ . . c y + 2δ]. For the case when a third run exists, denote ε = c xc y -(qp). The synchronizing interval is ε positions to the left compared to the one at (ii), that is,

I = [c x -δ -(q -p) -ε . . c x -δ -ε -1].
A third δ-close run would have to start again at i z = i x -(qp); see the bottom part of Fig. 3. Notice that z 2 smoothes out the non-periodic factors of length equal to ε (the small rectangles below the line in the bottom part of Fig. 3).

The interval with no other center of δ-runs is again J = [i z + 2(qp) . . e z -2(qp)].

(iv) i y ≤ i x < c x < c y (< e x < e y ). Here x and the prefix of length c xi y of y have period qp. As in case (ii) (the synchronizing interval I is the same) a third δ-close run z 2 would have to have the same beginning as y 2 , otherwise one of y 2 or z 2 would be left extendable. A fourth δ-close run would have to start at the same place and we can take here the same interval J; see Fig. 4. (The extra drawings show that we have the two (qp)-periods we need at the end of z.) One thing is a bit different. There can be δ-runs with center c x . They are accounted for as before, using case (i). Notice, however, that the period q does not extend completely to the left of c x . Still, the missing part is too small to affect the reasoning. (v) i x < i y (< c x < c y < e x < e y ). We have here a synchronizing interval as in (ii); see Fig. 5. A third δ close run z 2 would have to start, as in (iv), at the same place as y 2 and have the period q plus a multiple of qp. It would imply that w[i x . . i y -1] = w[c y -(i yi x ) . . c y -1] which would make y 2 left-extendable, a contradiction; see Fig. 5. Therefore, there cannot be a third run in this case.

We proved Proposition 1 There is at most 1 center of a δ-run on average in each interval of length δ.

Microruns

We prove in this section that the number of runs with periods at most 9, which we call microruns,4 in a string of length n is at most n. All runs we are talking about in this proof have periods at most 9.

The idea of the proof is as follows. We pick an arbitrary position i and consider all possible microruns with center at i. Then we show that the number of microruns with centers in an interval [ij . . i] is at most j where j can vary but is always less than 5. Put otherwise, any position with two or more centers of microruns is amortized within up to 4 previous positions to its left.

The number of possible subsets of periods at i is very high -2 9 = 512 -but we have the following lemma to help. It not only reduces significantly the number of cases but it helps with the analysis of each case as well.

Assume we have a string w. We shall say that w has p at i if there is a run with period p and center at position i in w. Denote also C(i) = {p | p at i}. (This set depends also on w but we shall consider w implicit and omit it.)

Note that there are two differences between (a run of period) p (and center) at i and a period p centered at i: the former is not left-extendable and its root is primitive whereas the latter may have none of the two properties. Lemma 1 Consider a string w and the periods p and pℓ, 0 < ℓ < p. Let h be the smallest integer such that hℓ ≥ p (h = ⌈p/ℓ⌉).

(i) (periods) If w has the period pℓ at i and the period p at i + j or ij with j ≤ ℓ, then w has the also periods pkℓ, 2 ≤ k ≤ h -1, at i.

(ii) (runs) If w has pℓ at i and either (a) p at i + j with j ≤ ℓ -1, or (b) p at ij with j ≤ ℓ, then w has pkℓ at i, for 2 ≤ k ≤ h -3 (that is, all but the shortest two).

Proof. (i) Assume p at i-j; the other case is completely symmetric. Assume also ℓ < p/2 since otherwise there is nothing to prove. Then w[i . . i+p-ℓ-1] = w[i-p . . i-ℓ-1] and the overlap between w[i-p . . i-ℓ-1] and w[i-(p-ℓ) . . i-1] gives that w[i-(p-ℓ) . . i-1] = w[i . . i+p-ℓ-1] has period ℓ. All periods at i claimed in the statement follow immediately.

(ii) Assume again p at ij but now j is strictly less than ℓ. We have the periods as claimed by (i). First, if ℓ divides p, then w[i -(pℓ) . . i -1] is not primitive, a contradiction. Therefore, ℓ does not divide p. Then, any w[i -(pkℓ) . . i -1], for 2 ≤ k ≤ h -3, must be primitive since otherwise, Fine and Wilf's lemma would imply that w[i -(pℓ) . . i -1] is not primitive, a contradiction. (The two shortest periods are not long enough to apply Fine and Wilf's lemma and indeed, they need not be primitive.)

For the non-left-extendability, we have w

[i -(p -kℓ) -1] = w[i -(p -ℓ) -1] = w[i -1].
Here we see the difference between (a) and (b): at (a) we need i

-(p -ℓ) -1 ≥ i + j -p, that is, j ≤ ℓ -1.
Another useful remark, with an obvious proof, is next. Remark 1 If we have p at i, then we cannot have p at j for any j, ip ≤ j ≤ i + p, j = i.

It is also obvious how Remark 1 is used. As far as Lemma 1 is concerned, it can be used in many ways. The first is, as already announced, to reduce as much as possible sets of periods of microruns with the same center. For instance, if we do not have periods 1,2,3 at i but do have 5, then we cannot have anything else: having 4 would imply having 1,2,3; 6 implies 1,2,3,4; 7 implies 1,3; 8 implies 2; 9 implies 1. This way our potential 512 cases are reduced to 26.

The lemma helps also with the analysis of each case, as seen in the proof of Lemma 2 below. Lemma 2 The number of runs with periods at most 9 in a string of length n is bounded by n.

Proof. We shall discuss in detail the analysis of one case and then give a list of all possible cases and the corresponding amortizing positions.

Consider, for example, the case when C(i) = {1, 3}. We shall use many times Lemma1 without mentioning. What we know so far about w is that w[i -4 . . i + 2] = aabaaba, where a = b and a means any letter different from a. The smallest element of C(i -1) is 5. If we have 5 at i -1, then w[i -7 . . i + 3] = baababaabab. Thus, C(i -1) = {5} and C(i -2) = ∅, which means that the two centers at i are amortized, in this case, within the previous two positions, since the total number of centers inside the interval [i -2 . . i] is 3. If there is not 5 at i -1, then the next that can be is 7 and the reasoning is identical. If there is not 7 at i -1, the next can be 8. If so, then C(i -1) = {8} and the only possible (but not necessary) candidate at i -2 is 2. If there is 2 at i -2 then C(i -2) = {2}, C(i -3) = ∅, and in this case the two centers at i are amortized within the previous three positions.

The reasoning continues like this until all possibilities are completely analyzed. Actually the case C(i) = {1, 3} has the longest analysis and there are very few comparable ones. This is the reason why we proved the result for periods up to 9. For higher numbers it gets quickly too complicated.

We give in Table 2 a list of tuples which consider all possible sets of periods of microruns with centers at an arbitrary position i and the corresponding possible sets of periods of microruns at the positions to the left of i, as many as needed to amortize them. Other sets are impossible due to Lemma 1. Thus, if the tuple contains, say, j elements, that means the tuple represents (C(ij + 1), C(ij + 2), . . . , C(i)). Here is the list, which the reader can verify himself using a similar reasoning as the one above; the list gives the pairs in the order they result from the proof, that is, increasing lexicographical order where the components corresponding to higher positions are more significant.

Table 2

The amortizing positions for the proof of Lemma 2.

i -3 i -2 i -1 i ∅ {5} {1, 3} ∅ {7} {1, 3} ∅ {2} {8} {1, 3} ∅ {8} {1, 3} ∅ {2} {9} {1, 3} ∅ {9} {1, 3} ∅ {1, 3} ∅ {1} {7} {1, 4} ∅ {7} {1, 4} ∅ {1} {9} {1, 4} ∅ {9} {1, 4} ∅ {1, 4} ∅ {1} {9} {1, 5} ∅ {9} {1, 5} ∅ {1, 5} ∅ {1, 6} ∅ {3} {1, 7} ∅ {1, 7} ∅ {3} {1, 8} ∅ {1, 8} ∅ {3} {1, 9} ∅ {1} {4} {1, 9} ∅ {4} {1, 9} ∅ {1, 9} i -3 i -2 i -1 i ∅ {1} {8} {2, 5} ∅ {8} {2, 5} ∅ {2, 5} ∅ {2, 6} ∅ {2, 7} ∅ {2, 8} ∅ {2, 9} ∅ {1} {3, 7} ∅ {3, 7} ∅ {1} {3, 8} ∅ {3, 8} ∅ {1} {3, 9} ∅ {3, 9} ∅ {1} {4, 9} ∅ {4, 9} ∅ {1} {5, 8} i -4 i -3 i -2 i -1 i ∅ ∅ {7} {1, 3, 5} ∅ {7} ∅ {1, 3, 5} ∅ ∅ {1, 3, 5} ∅ ∅ {1, 3, 7} ∅ {2} ∅ {1, 3, 8} ∅ ∅ {1, 3, 8} ∅ {2} ∅ {1, 3, 9} ∅ ∅ {1, 3, 9} ∅ {1} ∅ {1, 4, 7} ∅ ∅ {1, 4, 7} ∅ {1} ∅ {1, 4, 9} ∅ ∅ {1, 4, 9} ∅ {1} ∅ {1, 5, 9} ∅ ∅ {1, 5, 9} ∅ {1} ∅ {2, 5, 8} ∅ ∅ {2, 5, 8} ∅ ∅ ∅ {9} {1, 3, 5, 7} ∅ ∅ {9} ∅ {1, 3, 5, 7} ∅ {9} ∅ ∅ {1, 3, 5, 7} ∅ ∅ ∅ {1 , 3, 5, 7}
∅ ∅ ∅ ∅ {1, 3, 5, 7, 9}

Sum of exponents

We give in this section our bound on the sum of exponents which relies heavily on the results we have proved so far. The strategy is similar. We show that the sum of exponents of runs with periods four or less is at most 2n. Lemma 3 The sum of exponents of runs with periods at most 4 in a string of length n is bounded by 2n.

Proof. The idea is similar to the one in the proof of Lemma 2 except that here it is not clear how many positions we need to check. The problem is that exponents can be arbitrarily large and therefore no fixed-size interval can amortize them. Therefore, we need some changes. First, we shall choose the intervals to the right, as that is the direction in which the exponents increase. Second, we shall amortize periods and not runs, that is, in our arguments we shall not use the non-left-extendability of runs. We need to do this in order to amortize different parts of the same run separately.

We shall say that w has period (p, e) at i if w[ip . . i + (e -1)p -1] has period p, e ≥ 2, and w[ip . . i -1] is primitive. (What is missing from having a run is the non-extendability.) Also, w has period (p, ) at i if it has (p, e) for some e.

Assume also that the maximum period allowed for the microruns in this section is max per = 4. We shall make the reasoning for an arbitrary max per though, so that it becomes clear that the whole procedure can be automatized.

Given a string w and a position i, we say that [i . . j] is an amortizing interval for i in w if The idea is to consider only those exponents which correspond to the parts of the runs that need to be amortized by the current interval [i . . j], that is, those parts that do not stretch past j more than p -1 positions. If a run stretches more than p positions past j, then there is at least a full square with center outside the interval and it will be amortized, if needed, by a disjoint interval.

All we need to prove is that there exists a fixed upper bound on the lengths of amortizing intervals for all strings and all positions. The general strategy consists of considering all possibilities of periods at a given position for which the sum of exponents is larger than 2. Then we look for an amortizing interval to the right. The exponents are considered according to the above formula and updated, if needed, when the interval is increased.

For max per = 4, we give in Table 3 all possibilities of periods and exponents that can be encountered. Each line gives the pairs (period, exponent) corresponding to all positions in the amortizing interval [i . . j], where j ≤ max per -1 = 3. Recall that the exponents represent only the amortized part; the period may continue past the end of the interval arbitrarily. Some exponents are ranges of the form s p . . s+o p , which means that the same entry is obtained for any exponent t p , for s ≤ t ≤ s + o. Just to give an example, let us discuss the case when both periods 1 and 3 appear at i. We have the factor w[i -3 . . i + 2] = abaaba. Notice that the exponent for period 1 at i is maximal. There is no exponent at i + 1 which is enough to amortize the exponents at i provided that the one for 3 does not extend to the right; we obtain the entry ({(1, 2), (3, 2)}, ∅). However, if the exponent for period 3 at i goes up to 7 3 , the fact that there is no exponent at i + 1 is no longer sufficient. We look therefore at position i + 2 where we find no exponent. This is enough to amortize the exponents at i (and i + 1) even in the case when the exponent for period 3 at i is 8 3 . We obtain the entry ({(1, 2), (3, 7 3 . . 8 3 )}, ∅, ∅). The length of the amortizing interval is 3, which means we need not consider the exponent 9 3 for the period 3 at i. If it exists, then the exponent 6 3 or larger corresponding to the period 3 at i + 3 will be dealt with outside the amortizing interval [i . . i+2] we used for i; in such a case, 5 3 units of the exponent will be reamortized.

For runs with periods higher than 4, we shall use the discussion in Section 4 and Fine and Wilf's lemma. The lemma can be rephrased as follows: For two primitive strings x and y, any powers x α and y β , α ≥ 2 and β ≥ 2, cannot have a common factor longer than |x| + |y| as such a factor would have also period gcd(|x|, |y|), contradicting the primitivity of x and y.

Theorem 2 The sum of exponents of runs in a string of length n is less than 5.6n.

Comments

A small improvement of our main result in Theorem 1 can be rather easily obtained as follows. We can make a better choice of the δ i s to cover all periods: δ 0 = 10 2 -covers the periods between 10 and 15, δ 1 = 16 2 -covers the periods between 16 and 24, δ i = 25 2 3 2 i-2 , for all i ≥ 2 -cover all periods larger than or equal to 25.

The bound becomes:

n + 2 10 + 2 16 + 2 25 ∞ i=2 2 3 i-2 n = 1.565n .
The method of choosing values can be extended in the same manner to all δ i s but the improvements to the final bound are less and less significant. One would have to modify the proof of Theorem 1 to accommodate these changes, which is not difficult to do, but we preferred to keep the proof simpler. One could also try to improve the interval [2δ . . 3δ] in the definition of δ-closeness but the reasoning becomes more complicated.

The proof technique in Section 5 can be automatized so that larger periods for microruns can be considered. If one can prove it, for instance, for microruns with periods up to 32, then the bound improves to 1.18n (here we kept the same interval [2δ . . 3δ] but included the improvement described above in this section, using better choice of the δ i s). A similar computer-aided approach can be applied to the bound on the sum of exponents which could be improved down to 2.9n, assuming one can verify that the result in Lemma 3 holds for runs with periods up to 20.

Actually solving the conjecture using the above approach may be possible. For instance, one could attempt to verify by computer that the number of runs with periods less than 40 is at most 0.85n (the remaining ones are less than 0.15n by our reasoning). An efficient implementation of our implicit algorithm, based on Lemma 1, that we used in the proof of Lemma 2 is necessary.

We need to comment a bit more here. Our approach essentially approximates the number of runs, as it is very difficult, if not impossible, to account for all runs in this way. Therefore, the fact that we can attempt solving the conjecture shows, on the one hand, that our approach must be very close to reality, that is, the approximation we obtain is very good, yet, on the other, we believe that the bound n is not optimal as we seem to be able to get too close to it. Recall however, that it has to be more than 0.92n, according to the lower bound of [START_REF] Franek | The maximum number of runs in a string[END_REF], that means, not too far away.

Another promising approach is extending Lemma 1 to cover all periods. Of course, removing the bound on the length of periods of microruns in Lemma 1 makes it identical to the conjecture but we believe that the proof supporting the result can be extended. Precisely, we conjecture that each position with two or more centers can be amortized within at most half of the length of the longest possible period of a run, that is, at most a quarter of the length of the string.

Further research

We discuss here several related problems. The first one is old but the others are proposed here.

Squares. As the number of all square occurrences in a string may be quadratic and that of primitively rooted square occurrences can still be superlinear, as already mentioned in the Introduction, it is natural to count squares, that is, each square is counted only once no matter how many occurrences it has. As proved by Fraenkel and Simpson [START_REF] Fraenkel | How many squares can a string contain?[END_REF], there are at most 2n squares in a string of length n. A simple proof has been given by Ilie [START_REF] Ilie | A simple proof that a word of length n has at most 2n distinct squares[END_REF]. Based on the numerical evidence, it has been conjectured that this number is actually less than n; see also Chapter 8 of [START_REF] Lothaire | Applied Combinatorics on Words[END_REF]. The best bound to date is 2n -Θ(log n) due to Ilie [START_REF] Ilie | A note on the number of squares in a word[END_REF].

Runs. In this paper we counted in fact occurrences of repetitions because the runs are defined as intervals. Inspired by the square problem, we may look at their associated strings and count only the number of runs associated with different strings. Notice that the number of nonequivalent runs and that of squares do not seem to be obviously related to each other. The same run may contain several distinct squares (e.g., ababa contains the squares abab and baba) but we can have also different runs corresponding to a single squares (e.g., aa and aaa can be different runs but only the square aa is involved).

(2 + ε) + -repetitions. A way to weaken the conjecture on the number of squares is to increase the exponent of the repetition. Given a non-negative ε, one could count only the number of repetitions of exponent 2 + ε or higher. We need first to make it precise what we are talking about. We count primitively rooted repetitions of exponent at least 2 + ε and having distinct roots. That is, x α and y β , x and y primitive, α ≥ 2 + ε, β ≥ 2 + ε, are different if and only if x = y.

This conjecture might be easier to prove. At least for 2 + ε = 1 + φ, where φ is the golden ratio, we can prove it immediately. We count each square at the position where its rightmost occurrence starts and show that no two distinct squares can have the same rightmost starting position. Assume x 1+φ is a prefix of y 1+φ and denote |x| = p < q = |y|. Then necessarily |x 1+φ | = (1 + φ)p > φq = |y φ | as otherwise x 1+φ would have another occurrence to the right. That means φ 2 p = (1 + φ)p > φq, or φp > q. Therefore, the overlap between the two runs has the length |x 1+φ | = (1 + φ)p = p + φp > p + q. By Fine and Wilf's lemma, this means x and y are powers of the same string and therefore not primitive, a contradiction.

(2ε) + -repetitions. This is similar to the previous problem except that now we consider repetitions of exponent 2ε or higher. Is the number of such maximal repetitions still linear? If this is false for any ε > 0, then 2 is the optimal threshold. Otherwise, the optimal threshold needs to be found.

Fig. 1 .

 1 Fig. 1. The runs with the same center in case (i).

Fig. 2 .

 2 Fig. 2. Relative position of x 2 , y 2 and z 2 in case (ii).

Fig. 3 .

 3 Fig. 3. Relative position of x 2 , y 2 and z 2 in case (iii).

Fig. 4 .

 4 Fig. 4. Relative position of x 2 , y 2 and z 2 in case (iv).

Fig. 5 .

 5 Fig. 5. Relative position of x 2 , y 2 and z 2 in case (v).

  w has period (p, ) at k max{e | w has (p, e) at k, k + p(e -2) ≤ j} ≤ 2(ji + 1) .

  2.5 . Other runs are [2 . . 3], [7 . . 8], [8 . . 11], [5 . . 10] and [1 . . 11].

Runs were introduced in[START_REF] Main | Detecting lefmost maximal periodicities[END_REF] under the name maximal periodicities; they are called m-repetitions in[START_REF] Kolpakov | On maximal repetitions in words[END_REF] and runs in[START_REF] Iliopoulos | A characterization of the squares in a Fibonacci string[END_REF].

By analogy with the microsatellites in bioinformatics; these correspond to the concatenation of short DNA sequences (1 to 4 nucleotides) that are similar.

Acknowledgements

We would like to thank Liviu Tinta for pointing out a couple of errors in Table 2.

 [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF]Research supported in part by CNRS. 2 Research supported in part by CNRS and NSERC.

Next consider a fixed δ and two δ-runs, x α and y β , α, β ∈ Q, and denote their periods |x| = p and |y| = q. The strings x α and y β cannot overlap more than 2.5 min(p, q) as otherwise Fine and Wilf's lemma would imply that x and y are not primitive, a contradiction. Therefore, their suffixes x α-2.5 and y β-2.5 (assuming the exponents large enough) cannot overlap at all. Therefore, the sum of exponents of δ-runs is at most 2.5 times the number of runs plus whatever exponent is left of each run after removing the prefix of exponent 2.5. For x α , that means α -2.5 = |x α-2.5 | |x| ≤ |x α-2.5 | 2δ and when summing up all these, as they cannot overlap, we obtain n 2δ . Assuming that the number of runs as above is at most n δ and using Lemma 3, we obtain the following bound on the sum of exponents, where

Notice however, that in our analysis from Section 4, for the case (i) of many runs with the same center, we accounted for some of the runs using other runs with periods belonging to a different δ-class. That means the number of runs for each δ need not be n δ . Still our bound is exact because the runs we account for in case (i) have very small exponents. Recall that we need to account, for each δ, for all runs but one. Using the notation from case (i), any run x αj j , 2 ≤ j ≤ h -1, cannot extend its period |x j | by more than ℓ positions to the right past the end of the initial square, and therefore has α j ≤ 2 + 1 j ≤ 2.5. The runs with the shortest and the longest periods, x α1 1 and x α h h , respectively, may have arbitrarily large exponents but we need not account for either one. The bound in (2) therefore holds and we proved