Cyril Allauzen
email: fallauzen@monge.univ-mlv.fr

Maxime Crochemore

? Mathieu

Ra Not

Factor oracle: a new structure for pattern matching

Keywords: indexing, nite automaton, pattern matching, algorithm design

We introduce a new automaton on a word p, sequence of letters taken in an alphabet , that we call factor oracle. This automaton is acyclic, recognizes at least the factors of p, has m + 1 states and a linear number of transitions. We give an on-line construction to build it. We use this new structure in string matching algorithms that we conjecture optimal according to the experimental results. These algorithms are as e cient as the ones that already exist using less memory and being more easy to implement.

Introduction

A word p is a nite sequence p = p 1 p 2 : : :p m of letters taken in an alphabet . We keep the notation p along this paper to denote the word on which we are working.

E cient pattern matching on xed texts are based on indexes built on top of the text. Many indexing techniques exist for this purpose. The simplest methods use precomputed tables of q-grams while more achieved methods use more elaborated data structures. These classical structures are: su x arrays, su x trees, su x automata or DAWGs 1 , and factor automata (see 11]). When regarded as automata, they accept the set of factors (substrings) of the text. All these structures lead to very time-e cient pattern matching algorithms but require a fairly large amount of memory space. It is considered, for example, that the implementation of su x arrays can be achieved using ve bytes per text character and that other structures need about twelve bytes per text character.

Several strategies have been developed to reduce the memory space required to implement structures for indexes.

One of the oldest method is to merge the compression techniques applied both by the su x tree and the su x automaton. It leads to the notion of compact su x automaton (or compact DAWG) 5]. The direct construction of this structure is given in [START_REF] Crochemore | Direct construction of compact directed acyclic word graphs[END_REF][START_REF] Crochemore | On compact directed acyclic word graphs[END_REF].

A second method to reduce the size of indexes has been considered in the text compression method in 10]. It consists in representing the complement language of the factors (substrings) of the text. More precisely, only minimal factors not occurring in the text need to be considered [START_REF] Crochemore | Minimal forbidden words and factor automata[END_REF][START_REF] Crochemore | Automata and forbidden words[END_REF]. Which allow to store them in a tree and to save space.

We present in this paper a third method. We want to build an automaton (a) that is acyclic (b) that recognizes at least the factors of p (c) that has the fewer states as possible and (d) that has a linear number of transitions. We already notice that such an automaton has necessarily at least m + 1 states.

The su x or factor automaton 4 We propose an intermediate structure that we call the factor oracle : an automaton with m + 1 states that satis es these four requirements.

We use this new structure to design new string matching algorithms. These algorithms have a very good average behaviour that we conjecture as optimal. The main advantages of these new algorithms are (1) that they are easy to implement for an optimal behaviour and (2) the memory saving that the factor oracle allows with respect to the su x automaton. The structure has been extended in 2] to implement the index of a nite set of texts.

The paper is structured as follows: Section 2 discusses the construction of the factor oracle, Section 3 describes a string matching based on the factor oracle and shows experimental results, and nally we conclude in Section 4. Proofs of the results presented in the paper may be found in 1]. We now de ne notions and de nitions that we need along this paper.

A word x 2 is a factor of p if and only if p can be written p = uxv with u; v 2 . We denote Fact(p) the set of all the factors of word p. A factor x of p is a pre x (resp. a su x) of p if p = xu (resp. p = ux) with u 2 . The set of all the pre xes of p is denoted by Pref(p) and the one of all the su xes Su (p). We say that x is a proper factor (resp. proper pre x, proper su x) of p if x is a factor (resp. pre x, su x) of p distinct from p and from the empty word . We denote pref p (i) the pre x of length i of p for 0 i jpj. We denote for u 2 Fact(p), poccur(u; p) = minfjzj ; z = wu et p = wuvg, the ending position of the rst occurrence of u in p.

Finally,we de ne for u 2 Fact(p) the set endpos p (u) = fi j p = wup i+1 : : :p m g.

If two factors u and v of p are such that endpos p (u) = endpos p (v), we denote u p v. It is very easy to verify that p is an equivalence relation; it is in fact the syntaxic equivalence of the language Su (p).

Construction algorithm

Build Oracle(p = p1p2 : : : pm) 1.

For i from 0 to m 2.

Create a new state i 3.

For i from 0 to m 1 4.

Build a new transition from i to i + 1 by pi+1 5.

For i from 0 to m 1 6.

Let u be a minimal length word in state i 7.

For all 2 ; 6 = pi+1 8.

If u 2 Fact(p i juj+1 : : : pm) 9.

Build a new transition from i to i + poccur(u ; p i juj+1 : : : pm) by The factor oracle of the word p = abbbaab is given as an example gure 2.

On this example, it can be noticed that the word aba is recognized whereas it is not a factor of p. Note: all the transitions that reach state i of Oracle(p) are labeled by p i . Lemma 1 Let u 2 be a minimal length word among the words recognized in state i of Oracle(p). Then, u 2 Fact(p) and i = poccur(u; p). Corollary 1 Let u 2 be a minimal length word among the words recognized in state i of Oracle(p), u is unique.

We denote min(i) the minimal length word of state i.

Corollary 2 Let i and j be two states of Oracle(p) such as j < i. Let u = min(i) and v = min(j), u can not be a su x of v.

Lemma 2 Let i be a state of Oracle(p) and u = min(i). u is a su x of any word c 2 which is the label of a path leading from state 0 to state i. Lemma 3 Let w 2 Fact(p). w is recognized by Oracle(p) in a state j poccur(w; p). Note: In lemma 3, j is really less or equal than poccur(w; p), and not always equal. The example given gure 3 represents the automaton Oracle(abbcabc), and the state reached after the reading of the word abc is strictly less than poccur(abc; abbcabc). Lemma 4 Let i be a state of Oracle(p) and u = min(i). Any path ending by u leads to a state j i.

Lemma 5 Let w 2 be a word recognized by Oracle(p) in i, then any su x of w is recognized in a state j i.

The number of states of Oracle(p) with p = p 1 p 2 : : :p m is m + 1. We now consider the number of transitions. Lemma 6 The number T Or (p) of transitions in Oracle(p = p 1 p 2 : : :p m ) satis es m T Or (p) 2m 1.

On-line algorithm

This section presents an on-line construction of the automaton Oracle(p), that means a way of building the automaton by reading the letters of p one by one from left to right. We denote repet p (i) the longest su x of pref p (i) that appears at least twice in pref p (i).

We de ne a function S p de ned on the states of the automaton, called supply function, that maps each state i > 0 of Oracle(p) to state j in which the reading of repet p (i) ends. We arbitrarily set S p (0) = 1. Notes: { S p (i) is well de ned for every state i of Oracle(p) (Corollary 3). { For any state i of Oracle(p), i > S p (i) (lemma 3).

We denote k 0 = m, k i = S p (k i 1 ) for i 1. The sequence of the k i is nite, strictly decreasing and ends in state 0. We denote CS p = fk 0 = m; k 1 ; : : :; k t = 0g the su x path of p in Oracle(p). Lemma 7 Let k > 0 be a state of Oracle(p) such that s = S p (k) is strictly positive. We denote w k = repet p (k) and w s = repet p (s). Then w s is a su x of w k .

Corollary 4 Let CS p = fk 0 ; k 1 : : :; k t = 0g be the su x path of p in Oracle(p) and let w i = repet p (k i 1 ) for 1 i t and w 0 = p. Then, for 0 < l t, w l is a su x of all the w i , 0 i < l t.

We now consider for a word p = p 1 p 2 : : :p m and a letter 2 the construction of Oracle(p ) from Oracle(p).

We denote Oracle(p) + the automaton Oracle(p) on which a transition by from state m to state m +1 is added. We already notice that a transition that exists in Oracle(p) + also exists in Oracle(p ), so that the di erence between the two automata may only rely on transitions by to state m + 1 that have to be added to Oracle(p) + in order to get Oracle(p ).

We are investigating states from which there may be transitions by to state m + 1.

Lemma 8 Let k be a state of Oracle(p) + such that there is a transition from k by to m + 1 in Oracle(p ). Then k has to be one of the states on the su x path CS p = fk 0 = m; k 1 ; : : :; k t = 0g in Oracle(p) + .

Among the states on the su x path of p, every state that has no transition by in Oracle(p) + must have one in Oracle(p ). More formally, the following lemma sets this fact. Lemma 9 Let k l < m be a state on the su x path CS p = fk 0 = m; k 1 ; : : :; k t = 0g of state m in Oracle(p = p 1 p 2 : : :p m ) + . If k l does not have a transition by in Oracle(p), then there is a transition by from k l to m + 1 in Oracle(p ).

Lemma 10 Let k l < m be a state on the su x path CS p = fk 0 = m; k 1 ; : : :; k t = 0g in Oracle(p = p 1 p 2 : : :p m ) + . If k l has a transition by in Oracle(p) + , then all the states k i ; 0 i t also have a transition by in Oracle(p) + .

The idea of the on-line construction algorithm is the following. According to the three lemmas 8, 9, 10, to transform Oracle(p) + in Oracle(p ) we only have to go down the su x path CS p = fk 0 = m; k 1 ; : : :; k t = 0g of state m and while the current state k l does not have an exiting transition by , a transition by to m + 1 should be added (lemma 9). If k l already has one, the process ends because, according to lemma 10, all the states k j after k l on the su x path already have a transition by .

If we only wanted to add a single letter, the preceding algorithm would be enough. But, as we want to be able to build the automaton by adding the letters of p the one after the other, we have to be able to update the supply function S p of the new automaton Oracle(p ). As (according to the de nition of S p ), the supply function of states 0 i m does not change from Oracle(p) to Oracle(p ), the only thing to do is to compute S p (m + 1). This is done with the following lemma. Lemma 11 If there is a state k d which is the greatest element of CS p = fk 0 = m; k 1 ; : : :; k t = 0g in Oracle(p) such that there is a transition by from k d to a state s in Oracle(p), then S p (m + 1) = s in Oracle(p ). Else S p = 0. Create Oracle( ) with: 2.

one single state 0 3.

S (0) 1 4.

For i 1 a m Do 5.

Oracle(p = p1p2 : : : pi) add letter(Oracle(p = p1p2 : : : pi 1),pi) 6.

End For

Figure5. On-line construction algorithm of Oracle(p = p1p2 : : : pm). Exemple The on-line construction of Oracle(abbbaab) is given gure 6.

String matching

The factor oracle of p can be used in the same way as the su x automaton in string matching in order to nd the occurrences of a word p = p 1 p 2 : : :p m in a text T = t 1 t 2 : : :t n both on an alphabet . The su x automaton is used in [START_REF] Czumaj | Speeding up two string-matching algorithms[END_REF][START_REF] Crochemore | Text algorithms[END_REF] to get an optimal algorithm in the average called BDM (for Backward Dawg matching). Its average complexity is in O(n log j j (m)=m) under a Bernouilli model of probability where all the letters are equiprobable.

The BDM algorithm move a window of size m on the text. For each new position of this window, the su x automaton of p r (the mirror image of p) is used to search for a factor of p from the right to the left of the window.

The basic idea of the BDM is that if this backward search failed on a letter after the reading of a word u then u is not a factor of p and moving the beginning of the window just after is secure. This idea is then re ned in the BDM using some properties of the su x automaton. However this idea is enough in order to get an e cient string matching algorithm. The most amazing is that the strict recognition of the factors (that the factor and su x automata allow) is not necessary. For the algorithm to work, it is enough to know that u is not a factor of p. The oracle can be used to replace the su x automaton as it is illustrated by gure 7. We call this new algorithm BOM for Backward Oracle Matching. The pseudo-code of BOM is given gure 3. Its proof is given lemma 13. We make the conjecture (according to the experimental results) that BOM is still optimal in the average. BOM(p = p1p2 : : : pm, T = t1t2 : : : tn)

EndWhile

Figure8. Pseudo-code of BOM algorithm. Lemma 13 The BOM algorithm marks all the occurrences of p in T and only them.

The worst-case complexity of BOM is O(nm). However, in the average, we make the following conjecture based on experimental results (see 3.2) :

Conjecture 1 Under a model of independance and equiprobability of letters, the BOM algorithm has an average complexity of O(n log j j (m)=m).

A linear algorithm in the worst case

Even if the preceding algorithms are very e cient in practice, they have a worstcase complexity in O(mn). There are several techniques to make the BDM algorithm (using su x automaton) linear in the worst case, and one of them can also be used to make our algorithms linear in the worst case. It uses the Knuth-Morris-Pratt (KMP) algorithm to make a forward reading of some characters in the text.

To explain the combined use of KMP and (factor or su x) oracle, we consider the current position before the search with the oracle : a pre x v of the pattern has already be read with KMP at the beginning of the search window and we start the backward search using the oracle from the right end of that current window. The end position of v in the current window is called critical position and is denoted by Critpos. The current position is schematized at gure 9.

Critpos Window v

Search with oracle Pre x of the pattern

Critical position

Figure9. Current position in the linear algorithm using both KMP and (factor or su x) oracle.

We use the search with the oracle from right to left from the right end of the window. We consider two cases whether the critical position is reached or not.

1. The critical position is not reached. The failure of the recognition of a factor occurs on character as in the general approach ( gure 7). We shift the window to the left until its beginning goes past character . We restart a KMP search on this new window rereading the characters already read by the oracle. This search stops in a new current position (with a new corresponding critical position) when the recognized pre x is small enough (less than m with 0 < < 1). The value of is discussed with the experimental results (see section 3.2), typically = 1=2. This situation is schematized gure 10. 2. The critical position is reached. We resume the KMP search from the critical position, from the state we were before stopping, rereading at least the characters read by the oracle. We then go on reading the text until the longest recognized pre x is small enough (less than ). This situation is schematized gure 11. This algorithm can be used with a backward search done with the factor oracle. We call this new algorithm Turbo-BOM. Concerning the complexity in the worst case, we have the following result.

Theorem 3 The algorithm Turbo-BOM is (i) linear considering the number of inspections of characters in the text. The number of these inspections is less than 2n.

(ii) linear considering the number of comparisons of characters. The number of these comparisons is less than 2n when the transitions of the oracle are available in O [START_REF] Allauzen | Factor oracle, Su x oracle[END_REF] and less than 2n+n log when the transitions are available in log .

Experimental results

In this section, we present the experimental results obtained. More precisely, we compare the following algorithms.

{ Sunday: the Sunday algorithm 15] is often considered as the fastest in practice, { BM: the Boyer-Moore algorithm 6], { BDM: the classical Backward Dawg Matching with a su x automaton 11], { Su : the Backward Dawg Matching with a su x automaton but without testing terminal states, this is equivalent to the basic approach with the factor automaton2 , { BOM: the Backward Oracle Matching with the factor oracle, { BSOM: the Backward Oracle Matching with the su x oracle. This later structure is not described in this version of the paper, but can be found in 1].

{ Turbo-BOM: the linear algorithm using BOM and KMP with = 1=2.

Our string matching experiments are done on random texts of size 10 Mb with an accuracy of +/-2% with a con dence of 95% (which may require thousands of iterations) for alphabets of size 2, 4, 16 and 32. The machine used is a PC with a Pentium II processor at 350MHz running Linux 2.0.32 operating system. For all the algorithms, the transitions of the automata are implemented as tables which allow O(1) branchs. But it is not realistic (especially for the su x automaton) when the alphabet becomes rather big (for instance for 16 bits character coding). Moreover, the Sunday algorithm becomes unusable as it is when the alphabet is big because it mainly uses character table.

Experimental results in string matching are always surprising because codes are small and the time taken by a comparison is not much greater than the time taken by an indice incrementation. It is for instance the reason why Sunday algorithm (when it is usable) is the fastest algorithm for small patterns. The window shift are very small but very few operations are necessary to get this shift. It is also the reason why BDM is slower than Su whereas the window shifts in BSOM and BDM are greater.

The 4 sub gures of gure 12 shows that BOM is as fast as Su (except on a binary alphabet) which is much more complicated and requires much more memory.

It is obviously useless (in the case of searchs in texts of characters) to mark and test terminal states in both su x automaton and factor oracle. Turbo-BOM algorithm is the slowest but it is the only one that can be used in real time and in that case its behavior is rather good. It has to be noticed that we arbitrarily set the value of to 1=2. However, according to the tests we have proceeded for di erent values of , it turns out that = 1=2 is the more often the best value and that the variations of search times with other values of (as far as they stay between (2 log j j m)=m and (m 2 log j j m)=m ) are not very signi cant and anyway do not deserve by themselves an accurate study. [START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF]

Conclusions

The new structure we presented, the factor oracle, allow new string matching algorithms. These algorithms are very e cient in practice, as e cient as the ones which already exists, but are far more simple to implement and require less memory. According to the experimental results, we conjecture that they are optimal on the average (under a model of equiprobability of letters) but it remains to be shown.

About the structure of factor oracle itself, many questions stay open. Among others, it would be interesting to have a characterization of the language recognized by the oracle.

It would also be interesting to have a study of the average number of external transitions in the oracle. It would give an idea of the average memory space required by the string matching algorithms. Finally, we notice that the factor oracle is not minimal considering the number of transitions among the automata of m + 1 states which recognize at least the factors. An example is given gure 13. This reduced automaton may also be used in string matching provided that its construction can be done in linear time. This construction remains an open problem.

  , 7] sati es (a)-(b)-(d) but not (c) whereas the sub-sequence automaton 3] satis es (a)-(b)-(c) but not (d), which makes the problem non trivial.

Figure1.

  Figure1. High-level construction algorithm of the Oracle

Figure2.

  Figure2. Factor oracle of abbbaab. The word aba is recognizes whereas it is not a factor.

Figure3.

  Figure3. Example of a factor (abc) that is not recognized at the end of his rst occurrence but before.

From

  Figure4. Add a letter to Oracle(p = p1p2 : : : pm) to get Oracle(p )

Figure6.

  Figure6. On-line construction of Oracle(abbaba). The dot-lined arrows represent the supply function.

Figure7.

  Figure7. Shift of the search window after the fail of the search by Oracle(p). The word u is not a factor of p.

  Figure10. First case : the critical position is not reached.

Figure12.

  Figure12. Experimental results in time of the string matching algorithms on random texts of size 10 Mb on alphabets of size 2, 4, 16 and 32. The X-axis represents the length of the pattern and the Y-axis the search time in 1/100th seconds per Mbytes

Figure13.

  Figure13. The factor oracle is not minimal considering the number of transitions among the automata of m + 1 states which recognize at least the factors.

The su x automaton without taking in account the terminal states (i.e. considering every state as terminal) and the factor automaton recognize the same language. The di erence is that the factor automaton is minimal, so its size is smaller or equal than the size of the su x automaton. But the di erence of size is not signi cant in practice, anyway not enough signi cant to justify the implementation of a factor automaton which will complicate and slow the preprocessing phase of the string matching algorithm.

\G enomes" of C.N.R.S.


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

Francesca Fiorenzi
email: fiorenzi@univ-mlv.fr

Dominique Perrin
email: perrin@univ-mlv.fr

A Hierarchy of Irreducible Sofic Shifts

Keywords:

We define new subclasses of the class of irreducible sofic shifts. These classes form an infinite hierarchy where the lowest class is the class of almost finite type shifts introduced by B. Marcus. We give effective characterizations of these classes with the syntactic semigroups of the shifts.

Introduction

Sofic shifts [START_REF] Weiss | Subshifts of finite type and sofic systems[END_REF] are sets of bi-infinite labels in a labeled graph. If the graph can be chosen strongly connected, the sofic shift is said to be irreducible. An irreducible sofic shift has a unique (up to isomorphisms of automata) minimal deterministic presentation called its right Fischer cover. A particular subclass of sofic shifts is the class of shifts of finite type which are defined by a finite set of forbidden blocks. Two sofic shifts X and Y are conjugate if there is a bijective block map from X onto Y . It is an open question to decide whether two sofic shifts are conjugate, even in the particular case of irreducible shifts of finite type.

Almost finite type shifts have been introduced in [START_REF] Marcus | Sofic systems and encoding data[END_REF] (see also [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts, Ergodic Theory Dynam[END_REF]). They constitute a meaningful intermediate class above the class of shifts of finite type for several reasons. For instance, if X is the shift presented by the reversed presentation of a shift X that has almost finite type, then X and X are conjugate [START_REF] Boyle | A note on minimal covers for sofic shifts[END_REF]. Almost finite type shifts are of practical interest in coding for constrained channels. Sliding block decoding theorems hold in the case of almost finite type constraints while they do not hold beyond this class [START_REF] Karabed | Sliding-block coding for input-restricted channels[END_REF].

In this article, we first give a characterization of almost finite type shifts based on the syntactic semigroup of the shift. This semigroup S is the transition semigroup of the right Fischer cover of the irreducible sofic shift. The structure of a finite semigroup is determined by the Green's relations (denoted R, L, H, D, J ), see for instance [START_REF] Pin | Varieties of Formal Languages[END_REF]. We show that an irreducible sofic shift has almost finite type if and only if for any regular H-class of S with image I and any Rclass of the D-class of rank 1 with domain D, the intersection D ∩ I has at most one element. In general, the greatest cardinality of D ∩ I, where I is an image and D is a domain as above, is called the degree of the shift. This enables the definition of a hierarchy of subclasses of irreducible sofic shifts with respect to this degree, where the lowest class (that with degree 1) is the class of almost finite type shifts. In particular, we prove that conjugate irreducible sofic shifts have the same degree. This degree is thus a conjugacy invariant.

The proof of this invariant uses Nasu's Classification Theorem for sofic shifts [START_REF]Topological conjugacy for sofic systems[END_REF] that extends William's one for shifts of finite type. This theorem says that two irreducible sofic shifts X, Y are conjugate if and only if there is a sequence of symbolic adjacency matrices of right Fischer covers A = A 0 , A 1 , . . . , A l-1 , A l = B, such that A i-1 and A i are elementary strong shift equivalent for 1 ≤ i ≤ l, where A and B are the adjacency matrices of the right Fischer covers of X and Y , respectively. This means that, for each i, there are two symbolic matrices U i and V i such that, after recoding the alphabets of A i-1 and A i , one has

A i-1 = U i V i and A i = V i U i .
A bipartite shift is associated in a natural way to a pair of elementary strong shift equivalent and irreducible sofic shifts [START_REF]Topological conjugacy for sofic systems[END_REF]. Another syntactic conjugacy invariant called the syntactic graph of the sofic shift was defined in [START_REF] Béal | The syntactic graph of a sofic shift[END_REF]. We give an example of two non-almost finite type shifts with different degrees (and therefore not conjugate) that have the same syntactic graph.

Basic definitions related to symbolic dynamics are given in Section 2.1. We refer to [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF] or [START_REF] Kitchens | Symbolic Dynamics: one-sided, two-sided and countable state Markov shifts[END_REF] for more details. See also [START_REF] Marcus | Sofic systems and encoding data[END_REF], [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]Section 13.1], [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts, Ergodic Theory Dynam[END_REF], [START_REF] Karabed | Sliding-block coding for input-restricted channels[END_REF], [START_REF] Blanchard | Codes engendrant certains systèmes sofiques[END_REF], [START_REF] Boyle | A note on minimal covers for sofic shifts[END_REF], [START_REF] Williams | Covers of non-almost-finite-type systems[END_REF] and [START_REF] Fiebig | Multiplicities of covers for sofic shifts[END_REF] about almost finite type shifts. Basic definitions and properties related to finite semigroups and their structure are given in Section 2.2. We refer to [START_REF] Pin | Varieties of Formal Languages[END_REF]Chapter 3] for a more comprehensive expository. Nasu's Classification Theorem is recalled in Section 2.3. In Section 3, we define a hierarchy of irreducible sofic shifts. In Section 4, we consider the problem of characterizing classes of shifts (as the class of almost finite type shifts), by algebraic properties of the syntactic semigroup.

Definitions and Background

Almost Finite Type Shifts and Their Presentations

Let A be a finite alphabet, i.e. a finite set of symbols. The shift map σ : A Z → A Z is defined by σ((a i ) i∈Z ) = (a i+1 ) i∈Z , for (a i ) i∈Z ∈ A Z . If A Z is endowed with the product topology of the discrete topology on A, a shift is a closed σ-invariant subset of A Z .

A finite automaton is a finite multigraph labeled by A. It is denoted A = (Q, E), where Q is a finite set of states, and E a finite set of edges labeled by A. It is equivalent to a symbolic adjacency (Q × Q)-matrix A, where A pq is the finite formal sum of the labels of all the edges from p to q. A sofic shift is the set of the labels of all the bi-infinite paths on a finite automaton. If A is a finite automaton, we denote by X A the sofic shift defined by the automaton A. Several automata can define the same sofic shift. They are also called presentations or covers of the sofic shift. We will assume that all presentations are essential : all states have at least one outgoing edge and one incoming edge. An automaton is deterministic if for any given state and any given symbol, there is at most one outgoing edge labeled by this given symbol. An automaton is left closing with delay D if whenever two paths of length D + 1 end at the same state and have the same label, then they have the same final edge. An automaton is left closing if it is left-closing with some delay D ≥ 0. A sofic shift is irreducible if it has a presentation with a strongly connected graph. Irreducible sofic shifts have a unique (up to isomorphisms of automata) minimal deterministic presentation, that is a deterministic presentation having the fewest states among all deterministic presentations of the shift. This presentation is called the right Fischer cover of the shift.

An irreducible sofic shift has almost finite type (AFT) if it has a deterministic and left-closing presentation. The class of almost finite type shifts was introduced by B. Marcus in [START_REF] Marcus | Sofic systems and encoding data[END_REF], see also [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts, Ergodic Theory Dynam[END_REF] and [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]Section 13.1].

Let A = (Q, E) be a deterministic automaton labeled by A. The square of A is the deterministic automaton (Q × Q, F ) where (p, q) a -→ (p , q ) ∈ F if and only if p a -→ p and q a -→ q ∈ E. A diagonal state of the square of A is a state (p, p), with p ∈ Q.

An almost finite type shift is an irreducible shift whose right Fischer cover is left-closing. Thus the square of its right Fischer cover has no strongly connected component with at least one edge containing a non-diagonal state and admitting a path going from this component to a diagonal state (see for instance [START_REF] Marcus | Sofic systems and encoding data[END_REF], [START_REF] Béal | Codage Symbolique[END_REF]). Checking whether an irreducible sofic shift has almost finite type can thus be done in a quadratic time in the number of states of the right Fischer cover of the shift.

The Syntactic Semigroup of an Irreducible Sofic Shift

In this section, we recall the definition and the structure of the syntactic semigroup of an irreducible sofic shift [START_REF] Béal | The syntactic graph of a sofic shift[END_REF].

Let A = (Q, E) be a finite deterministic (essential) automaton on the alphabet A. Each finite word w of A * defines a partial function from Q to Q. This function sends the state p to the state q, if w is the label of a path from p to q. The semigroup generated by all these functions is called the transition semigroup of the automaton. When X A is not the full shift, the semigroup has a null element, denoted 0, which corresponds to words which are not factors of any bi-infinite word of X A . The syntactic semigroup of an irreducible sofic shift is defined as the transition semigroup of its right Fischer cover.

Given a semigroup S, we denote by S 1 the following monoid: if S is a monoid, S 1 = S. If S is not a monoid, S 1 = S ∪ {1} together with the law * defined by x * y = xy if x, y ∈ S and 1 * x = x * 1 = x for every x ∈ S 1 .

We recall the Green's relations R, L, H, J , which are fundamental equivalence relations defined in a semigroup S. They are defined as follows. Let x, y ∈ S,

xRy ⇔ xS 1 = yS 1 , xLy ⇔ S 1 x = S 1 y, xJ y ⇔ S 1 xS 1 = S 1 yS 1 , xHy ⇔ xRy and xLy.
Another relation D is defined by: xDy ⇔ ∃z ∈ S xRz and zLy.

In a finite semigroup J = D.

An R-class is an equivalence class for a relation R (similar notations hold for the other Green's relations). An idempotent is an element e ∈ S such that ee = e. A regular class is a class containing an idempotent. In a regular D-class, any H-class containing an idempotent is a maximal subgroup of the semigroup. Moreover, two regular H-classes contained in a same D-class are isomorphic (as groups), see for instance [START_REF] Pin | Varieties of Formal Languages[END_REF]Chapter 3 Proposition 1.8].

We say that two elements x, y ∈ S are conjugate if there are elements u, v ∈ S 1 such that x = uv and y = vu.

Let S be a transition semigroup of an automaton A = (Q, E) and x ∈ S. The rank of x is the cardinal of the image of x as a partial function from Q to Q. The kernel of x is the partition induced by the equivalence relation ∼ over the domain of x where p ∼ q if and only p, q have the same image under x. We describe the so called "egg-box" pictures with the sofic shifts of Figure 1 and Figure 2 which have almost finite type and not almost finite type, respectively. The syntactic semigroup of an irreducible sofic shift has a unique D-class of rank 1 which is regular (see for instance [START_REF] Beauquier | Minimal automaton for a factorial transitive rational language[END_REF] or [START_REF] Berstel | Theory of Codes[END_REF], and also [START_REF] Jonoska | A conjugacy invariant for reducible sofic shifts and its semigroup characterizations[END_REF]). Moreover, if u is a non null element of this semigroup, there is a word w such that uw has rank 1.

Nasu's Classification Theorem for Sofic Shifts

In this section, we recall Nasu's Classification Theorem for sofic shifts [START_REF]Topological conjugacy for sofic systems[END_REF] (see also [12, Theorem 7.2.12]), which extends William's Classification Theorem for shifts of finite type (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]Theorem 7.2.7]). Let X ⊂ A Z , Y ⊂ B Z be two shifts and m, a be nonnegative integers. A map φ : X → Y is a (m, a)-block map (or (m, a)-factor map) if there is a map δ :

A m+a+1 → B such that φ((a i ) i∈Z ) = (b i ) i∈Z where δ(a i-m . . . a i-1 a i a i+1 . . . a i+a ) = b i .
A block map is a (m, a)-block map for some nonnegative integers m, a (respectively called its memory and anticipation). The well known theorem of Curtis, Hedlund, and Lyndon [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF] asserts that continuous maps commuting with the shift map σ, are exactly block maps. A conjugacy is a one-to-one and onto block map (then, being a shift compact, also its inverse is a block map).

Having almost finite type is a property of shifts which is invariant under conjugacy [START_REF] Marcus | Sofic systems and encoding data[END_REF].

Let A be the symbolic adjacency (Q × Q)-matrix of an automaton A with entries in a finite alphabet A. Let B be a finite alphabet and f a one-to-one map from A to B. The map f is extended to a morphism from finite formal sums of elements of A to finite formal sums of elements of B. We say that f transforms

A into a symbolic (Q × Q)-matrix B if B pq = f (A pq ) for each p, q ∈ Q.
We now define the notion of strong shift equivalence between two symbolic adjacency matrices.

Let A and B be two finite alphabets. We denote by AB the set of words ab with a ∈ A and b ∈ B.

Two symbolic matrices A and B with entries in A and B respectively, are elementary strong shift equivalent if there is a pair of symbolic matrices (U, V ) with entries in disjoint alphabets U and V respectively, such that there is a oneto-one map from A to UV which transforms A into U V , and there is a one-to-one map from B to VU which transforms B into V U.

Two symbolic adjacency matrices A and B are strong shift equivalent within right Fischer covers if there is a sequence of symbolic adjacency matrices of right Fischer covers

A = A 0 , A 1 , . . . , A l-1 , A l = B
such that for 1 ≤ i ≤ l the matrices A i-1 and A i are elementary strong shift equivalent.

Theorem 1 (Nasu). Let X and Y be irreducible sofic shifts and let A and B be the symbolic adjacency matrices of the right Fischer covers of X and Y , respectively. Then X and Y are conjugate if and only if A and B are strong shift equivalent within right Fischer covers.

Let us consider the two irreducible sofic shifts X and Y defined by the right Fischer covers in Figure 3. The symbolic adjacency matrices of these automata are respectively

A = a b b 0 , B =   a 0 d c 0 b 0 b 0   .
Then A and B are elementary strong shift equivalent with

U = u 1 0 u 2 0 u 2 0 , V =   v 1 0 v 2 0 0 v 2   .
Indeed,

U V = u 1 v 1 u 2 v 2 u 2 v 2 0 , V U =   v 1 u 1 0 v 1 u 2 v 2 u 1 0 v 2 u 2 0 v 2 u 2 0   .
The one-to-one maps from A = {a, b} to UV and from B = {a , b , c , d } to VU are described in the tables below.

a u 1 v 1 b u 2 v 2 , a v 1 u 1 b v 2 u 2 c v 2 u 1 d v 1 u 2 .
An elementary strong shift equivalence between A = (Q, E) and B = (Q , E ), enables the construction of an irreducible sofic shift Z on the alphabet U ∪ V as follows. The sofic shift Z is defined by the automaton C = (Q ∪ Q , F ), where the symbolic adjacency matrix

C of C is Q Q Q Q 0 U V 0 .
The shift Z is called the bipartite shift defined by U, V (see Figure 4). An edge of C labeled by U goes from a state in Q to a state in Q . An edge of C labeled by V goes from a state in Q to a state in Q. Remark that C is a right Fischer cover (i.e. is minimal).

A Hierarchy of Irreducible Sofic Shifts

In this section, we first give a syntactic characterization of almost finite type shifts. Next, we define a hierarchy of irreducible sofic shifts. Proof Let us assume that X has not almost finite type. Let A be the right Fischer cover of X. Then there are two states p = q and a state r, two words u, v and two paths on A labeled uv as follows.

p u -→ p v -→ r q u -→ q v -→ r
There is a positive integer n that u n is a non null idempotent in S. Let I be the image of u n . It contains p and q. Let w be a word of rank 1 in S. Since A has a strongly connected graph, there is a word w such that the domain of w w contains the state r. The word vw w has rank 1 and its domain contains p and q. Thus the intersection of the domain of vw w and I contains at least two elements.

Conversely, let us assume that there is in S a regular H-class H with image I and an R-class R of the D-class of rank 1 with domain D, such that D ∩ I has at least two elements. Let e be an idempotent of H. Then e induces the identity map on its image I. Let p = q ∈ D ∩ I, and v ∈ R. Then there is a state r and two paths on A as follows

p e -→ p v -→ r q e -→ q v -→ r
It follows that X has not almost finite type.

For instance, the shift presented in Figure 2 The following proposition allows us to prove that the class of irreducible sofic shifts with degree d is a class of shifts invariant under conjugacy. In this classification, the class of almost finite type shifts is the class of irreducible sofic shifts with degree 1. This enables to recover that the property of having almost finite type is a conjugacy invariant. Before proving Proposition 2, we recall some results from [START_REF] Béal | The syntactic graph of a sofic shift[END_REF] about the syntactic semigroup of a bipartite shift. Let X (respectively Y ) be an irreducible sofic shift whose symbolic adjacency matrices of its right Fischer cover is a (Q × Q)matrix (respectively (Q × Q )-matrix) denoted by A (respectively by B). We assume that A and B are elementary strong shift equivalent through a pair of matrices (U, V ). The corresponding alphabets are denoted A, B, U, and V as before. We denote by f a one-to-one map from A to UV which transforms A into U V and by g a one-to-one map from B to VU which transforms B into V U. Let Z be the bipartite irreducible sofic shift associated to U, V . We denote by S (respectively T , R) the syntactic semigroup of X (respectively Y , Z).

Let w ∈ R. If w is non null, the bipartite nature of Z implies that w is a function from Q∪Q to Q∪Q whose domain is included either in Q or in Q , and whose image is included either in Q or in Q . If w = 0 with a domain included in P and an image included in P , we say that w has the type (P, P ). Remark that w has type (Q, Q) if and only if w = 0 and w ∈ (f (A)) * , and w has type (Q , Q ) if and only if w = 0 and w ∈ (g(B)) * . Elements of R in a same non null H-class have the same type.

Let w = a 1 . . . a n be an element of S, we define the element f (w) as f (a 1 ) . . . f (a n ). Note that this definition is consistent since if a 1 . . . a n = a 1 . . . a m in S, then f (a 1 ) . . . f(a n ) = f (a 1 ) . . . f(a m ) in R. Similarly we define an element g(w) for any element w of T .

Conversely, let w be an element of R belonging to f (A) * (⊂ (UV) * ). Then w = f (a 1 ) . . . f(a n ), with a i ∈ A. We define f -1 (w) as a 1 . . . a n . Similarly we define g -1 (w). Again these definitions and notations are consistent. Thus f is a semigroup isomorphism from S to the subsemigroup of R of transition functions defined by the words in (f (A)) * . Notice that f (0) = 0 if 0 ∈ S. Analogously, g is a semigroup isomorphism from T to the subsemigroup of R of transition functions defined by the words in (g(B)) * .

We now prove Proposition 2.

Proof[of Proposition 2] By Nasu's Theorem [START_REF]Topological conjugacy for sofic systems[END_REF] we can assume, without loss of generality, that the symbolic adjacency matrices of the right Fischer covers of X and Y are elementary strong shift equivalent. We define the bipartite shift Z as above. We denote by S, T and R the syntactic semigroups of X, Y and Z respectively.

Let us assume that X is d-non-left closing. Thus S has a regular H-class H with image I and an R-class of the D-class of rank 1 with domain D, such that D ∩ I has d elements. Let e be an idempotent of H. It induces the identity map on its image I.

The element f (e) is an idempotent element of type

(Q, Q) in R. Let u 1 v 1 . . . u n v n ∈ (UV) * such that f (e) = u 1 v 1 . . . u n v n .
We define an element ē as ē = v 1 . . . u n v n u 1 . Thus f (e)u 1 = u 1 ē in R. Remark that ē depends on the choice of the word u 1 v 1 . . . u n v n representing f (e) in R. Notice that ē and f (e) are conjugate. Indeed, if w = v 1 . . . u n v n , then f (e) = u 1 w and ē = wu 1 . Hence, ē3 = wu 1 wu 1 wu 1 = wf (e) 2 u 1 = wf (e)u 1 = wu 1 wu 1 = ē2 . We have ē2 = 0 since f (e) = 0 and f (e) = f (e) 2 = f (e) 3 = u 1 ē2 w. Thus ē2 is an idempotent of R of type (Q , Q ).

Let I ∩ D = {x 1 , . . . , x d }. Then there is a word z ∈ A * of rank 1, a state x ∈ Q and a path on the right Fischer cover of X labeled z from any state in I ∩ D to x. Moreover, there are a letter u ∈ U, a state y ∈ Q and an edge x u -→ y in the right Fischer cover of Z. It follows that there are paths as follows in the right Fischer cover of Z.

x 1 u1 -→ y 1 w -→ x 1 u1 -→ y 1 w -→ x 1 f (z) ---→ x u -→ y x 2 u1 -→ y 2 w -→ x 2 u1 -→ y 2 w -→ x 2 f (z) ---→ x u -→ y . . . x d u1 -→ y d w -→ x d u1 -→ y d w -→ x d f (z) ---→ x u -→ y
The states y i , for 1 ≤ i ≤ d, belong to Q . Since the states x i are distinct, also the states y i are distinct. Indeed, let us assume for instance that y 1 = y 2 . Then x 1 = x 2 by considering the paths labeled w from y i to x i for i = 1, 2. Thus, in the right Fischer cover of Z there are the following paths, for 1 ≤ i ≤ d. Notice that e is an idempotent of T . Since the graph of the right Fischer cover of Y is strongly connected, there is a word w of rank 1 whose domain contains y. This allows us to assume that the word w is an element of rank 1 of T . Hence the domain D of the R-class of w and the image I of the idempotent e , contain {y 1 , . . . , y d }. We now prove that D ∩ I is exactly the set {y 1 , . . . , y d }.

Suppose that there is a state ȳ ∈ D ∩ I such that ȳ = y i for each i. Hence the following path is in the right Fischer cover of Y . ȳ e -→ ȳ w -→ y Thus, in the right Fischer cover of Z there is the following path.

ȳ (wu1) 2 ----→ ȳ wf (z)u ----→ y
Let x be the final state of the path labelled by w and starting at ȳ. It follows that a path of the kind

ȳ w -→ x u1 -→ . w -→ . u1 -→ ȳ w -→ x f (z) ---→ x
is in the right Fischer cover of Z (recall that f (z) has rank 1). Being x in the image of u 1 wu 1 w = f (e) 2 = f (e), we have that x in the image I of e. Moreover, x is in the domain of f (z) and hence it is also in the domain D of z. This implies that x is one of the elements x i and hence ȳ is the corresponding y i , which is a contradiction. Thus the cardinality of D ∩ I is d.

We get the following corollary.

Corollary 1. Let X be an irreducible sofic shift. Then its degree is invariant under conjugacy. Moreover, the increasing sequence (d 1 , d 2 , . . . , d n ) of positive integers such that X is d i -non-left closing (where d n is the degree of the shift), is invariant under conjugacy.

We show in Figure 5 an example of two sofic shifts X and Y , where X has not almost finite type with degree 3, and Y has not almost finite type with degree 2. Thus these two shifts are not conjugate since their degrees are different. Remark that they have the same syntactic graph, which is another conjugacy invariant defined and described in [START_REF] Béal | The syntactic graph of a sofic shift[END_REF].

There are irreducible sofic shifts with degree d for every d >

Links with Semigroup Theory

The above propositions have links with previous results in the theory of varieties of semigroups.

A finite biprefix code (see for instance [START_REF] Berstel | Theory of Codes[END_REF]) defines an almost finite type shift in a natural way. It is known from [START_REF] Margolis | On the syntactic transformation semigroup of a language generated by a finite biprefix code[END_REF] that, if X is a finite biprefix code and S the syntactic semigroup of X + , eSe defines a semigroup of partial injective transformations for any idempotent e. Margolis [START_REF] Margolis | On the syntactic transformation semigroup of a language generated by a finite biprefix code[END_REF] also showed that every semigroup of partial injective transformations divides a semigroup of partial injective transformations which is the syntactic semigroup of a finite biprefix code.

An equivalent formulation of Proposition 1 is the following.

Proposition 3. Let X an irreducible sofic shift and S its syntactic semigroup. Then X has almost finite type if and only if for any idempotent e ∈ S, the semigroup eSe is a semigroup of partial one-to-one transformations.

Thus, when S has almost finite type, the semigroup eSe is, for any idempotent e, a subsemigroup of an inverse semigroup. This implies that the semigroup S belongs to the variety of semigroups T such that for each idempotent e, the semigroup eT e is in the variety generated by inverse semigroups. We do not know whether this condition is sufficient to guarantee that X has almost finite type.

Fig. 1 .

 1 Fig. 1. An irreducible sofic shift which has almost finite type. Its syntactic semigroup is represented on the right part of the figure. It is composed of three D-classes of rank 2, 1 and 0, respectively, represented by the above tables from left to right. Each square in a table represents an H-class. Each row represents an R-class and each column an L-class. The common kernel of the elements in each row is written on the left of each row. The common image of the elements in each column is written above each column. Idempotents are marked with the symbol * . Each D-class of this semigroup is regular.

Fig. 2 .

 2 Fig.2. An irreducible sofic shift which has not almost finite type. Indeed, there are two distinct left-infinite paths labelled ...bbbbbba ending at state 2. Also in this case, each D-class is regular.

Fig. 3 .

 3 Fig. 3. Two conjugate shifts X and Y .

Fig. 4 .

 4 Fig. 4. The bipartite shift Z of the shifts X and Y in Figure 3.

Proposition 1 .

 1 Let X be an irreducible sofic shift and S its syntactic semigroup. Then X has almost finite type if and only if for any regular H-class of S with image I and any R-class of the D-class of rank 1 with domain D, the intersection D ∩ I has at most one element.

  has not almost finite type since it has a regular H-class of rank 2 (containing the idempotent b) whose image is {1, 2}. This image intersects the domain of {ac, a} (which is a R-class contained in the D-class of rank 1), with {1, 2} as intersection. We now introduce the following classification of irreducible sofic shifts. An irreducible sofic shift is d-non-left closing if its syntactic semigroup has a regular H-class with image I and an R-class of the D-class of rank 1 with domain D, such that D ∩ I has d elements. An irreducible sofic shift has degree d if it is d-non-left closing with d ≥ 0 and not d -non-left closing for any d > d. Notice that the degree of an irreducible sofic shift is always non null.

Proposition 2 .

 2 Let X and Y be two conjugate irreducible sofic shifts and let d be a positive integer. If X is d-non-left closing, then Y is d-non-left closing.

  Since ē = wu 1 and wf (z)u are contained in (g(B)) * , the elements e = g -1 (ē 2 ) = g -1 ((wu 1 ) 2 ) and w = g -1 (wf (z)u) are in T . Hence the following paths are in the right Fischer cover of Y , for 1 ≤ i ≤ d.

Fig. 5 .

 5 Fig. 5. The right Fischer covers of two non conjugate sofic shifts X (on the left) and Y (on the right), with A = {a, b, x, y, z} and B = {a, b, c, x, y, z}. The shift X has degree 3 while the shift Y has degree 2.

1 .

 1 For instance, consider the right Fischer cover A = ({1, 2, . . . , d, d + 1}, E) on the alphabet A = {a, b, c}, where the set of edges is E = {ib -→ i, i a -→ d + 1 | i = d + 1} {i c -→ i -1 | 2 ≤ i ≤ d} {d + 1 c -→ d}.This right Fischer cover has degree d.

Acknowledgment

The authors wish to thank the reviewer who suggested the second statement of Corollary 1.


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

Dominique Perrin
email: perrin@univ-mlv.fr

Complete codes in a sofic shift

We define a code in a sofic shift as a set of blocks of symbols of the shift such that any block of the shift has at most one decomposition in code words. It is maximal if it is not strictly included in another one. Such a code is complete in the sofic shift if any block of the shift occurs within some concatenation of code words. We prove that a maximal code in an irreducible sofic shift is complete in this shift. We give an explicit construction of a regular completion of a regular code in a sofic shift. This extends the well known result of Ehrenfeucht and Rozenberg to the case of codes in sofic systems. We also give a combinatorial proof of a result concerning the polynomial of a code in a sofic shift.

Introduction

In this paper, we continue the study of codes in sofic shifts initiated in [START_REF] Béal | Codes and sofic constraints[END_REF]. This generalization of the theory of (variable length) codes extends previous works of Reutenauer [START_REF] Reutenauer | Ensembles libres de chemins dans un graphe[END_REF], Restivo [START_REF] Restivo | Codes and local constraints[END_REF] and Ashley et al. [START_REF] Ashley | Surjective extensions of sliding-block codes[END_REF]. The main result of this paper is an extension of a classical result of Schützenberger [START_REF] Berstel | Theory of codes[END_REF] relating the notions of completeness and maximality of codes.

Let S be a sofic shift, i.e. the set of bi-infinite sequences of symbols labelling paths in a finite automaton. The set of factors of S, denoted by Fact(S), is the set of blocks appearing in the elements of S. We call S-code a set of elements of Fact(S) such that any element of Fact(S) has at most one decomposition in code words. A set of words X is S-complete if any element of Fact(S) occurs within some concatenation of elements of X. An S-code is maximal if it is maximal for inclusion.

We prove that, for any irreducible sofic shift S, any maximal S-code is Scomplete. Moreover, we give an effective embedding of a regular S-code into an S-complete one. This extends the well known theorem of Ehrenfeucht and Rozenberg [START_REF] Ehrenfeucht | Each regular code is included in a maximal regular code[END_REF] to codes in a sofic shift.

Our definition of S-codes generalizes the notion introduced by Restivo [3] and Ashley et al. [START_REF] Ashley | Surjective extensions of sliding-block codes[END_REF]. In the first place, they consider subshifts of finite type instead of the more general notion of sofic shifts. Although shifts of finite type can also be described by a finite automaton, there is a real gap between the two classes. Indeed, representations of shifts of finite type have nice strong properties of synchronization that do not have general sofic shifts. These properties are used to complete the codes. In the second place, they consider codes such that all concatenations of code words are in Fact(S), a condition that we do not impose. Our definition here is also slightly more general than the one used in our previous paper [START_REF] Béal | Codes and sofic constraints[END_REF]. Indeed, we only require the unique factorization for the words of Fact(S) and not for all products of code words. We think that this definition is more natural. The results of [START_REF] Béal | Codes and sofic constraints[END_REF] all extend straightforwardly to this new class.

In the last section, we give a combinatorial proof of the main result of our previous paper [START_REF] Béal | Codes and sofic constraints[END_REF] concerning the polynomial of a finite code. This proof is interesting because it is simpler and also because it relates our result to ones due to S. Williams [START_REF] Williams | Lattice invariants for sofic shifts[END_REF] and M. Nasu [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts[END_REF].

The paper is organized as follows. We first recall some basic definitions from the area of symbolic dynamics and from the theory of codes. We introduce the notions of S-code, maximal S-code, and S-complete code when S denotes a sofic shift. In Section 3, we prove that any maximal S-code is S-complete. A combinatorial proof of the result of [START_REF] Béal | Codes and sofic constraints[END_REF] is given in the last section.

Codes and Sofic Shifts

Sofic Shifts

Let A be a finite alphabet. We denote by A * the set of finite words, by A + the set of nonempty finite words, and by A Z the set of bi-infinite words on A. A subshift is a closed subset S of A Z which is invariant by the shift transformation σ (i.e. σ(S) = S) defined by σ((a i ) i∈Z ) = (a i+1 ) i∈Z .

A finite automaton is a finite multigraph labeled on a finite alphabet A. It is denoted A = (Q, E), where Q is a finite set of states, and E a finite set of edges labeled by A. All states of these automata can be considered as both initial and final states.

A sofic shift is the set of labels of all bi-infinite paths in a finite automaton. A sofic shift is irreducible if there is such a finite automaton with a strongly connected graph. In this case the automaton also is said to be irreducible. An automaton A = (Q, E) is deterministic if, for any state p ∈ Q and any word u, there is at most one path labeled u and going out of p. When it exists, the target state of this path is denoted by p • u. An automaton is unambiguous if there is at most one path labeled by u going from a state p to a state q for any given triple p, u, q. Irreducible sofic shifts have a unique (up to isomorphisms of automata) minimal deterministic automaton, that is a deterministic automaton having the fewest states among all deterministic automata representing the shift. This automaton is called the Fischer cover of the shift. A subshift of finite type is defined as the bi-infinite words on a finite alphabet avoiding a finite set of finite words. It is a sofic shift. The full shift on the finite alphabet A is the set of all bi-infinites sequences on A, i.e. the set A Z .

The entropy of a sofic shift S is defined as

h(S) = lim n→∞ 1 n log 2 s n ,
where s n is the number of words of length n of Fact(S). The Fischer cover of a transitive sofic shift of null entropy is made of one cycle.

Example 1. Let S be the irreducible sofic subshift on A = {a, b} defined by the automaton on the left of Figure 1. This automaton is the Fischer cover of S. This shift is the so-called even system since its bi-infinite sequences are those having an even number of b's between two a's. It is not a shift of finite type.

Let T be the irreducible shift on A = {a, b} defined by the forbidden block bb. It is a shift of finite type. Its Fischer cover is given on the right of Figure 1. This shift is the so-called golden mean system. Let S be a subshift on the alphabet A. We denote by Fact(S) the set of finite factors (or blocks) of elements of S. Each element of Fact(S) is the label of a finite path of the Fischer cover of S.

Let A be a finite automaton. A word w is said to be a synchronizing word of A if and only if any path in A labeled by w ends in a same state depending only on w. If p denotes this states, one says that w synchronizes to p. For instance the words a, bab are synchronizing words of the Fischer cover of the even system. In the golden mean shift, which is a shift of finite type, each word of length 1, i.e. a or b, is a synchronizing word. For any Fischer cover of a shift of finite type, there is a positive integer k such that any word of length k is synchronizing.

Let L be a language of finite words. A word w is a synchronizing word of L if and only if whenever u, v are words such that uw and wv belong to L, one has uwv belongs to L. Note that if w is a synchronizing word of an automaton A recognizing a sofic shift S, it is a synchronizing word of the language Fact(S).

It is known that the Fischer cover of an irreducible sofic shift S has a synchronizing word [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]Proposition 3.3.16]. If w is one of them, for any words u, v such that uwv ∈ Fact(S), uwv is a synchronizing word also.

Codes

Let S be a sofic shift. A set of finite words X ⊂ Fact(S) on an alphabet A is an S-code if and only if whenever w = x 1 x 2 . . . x n = y 1 y 2 . . . y m , where x i , y j ∈ X, n, m are positive integers, and w ∈ Fact(S), one has n = m and x i = y i for 1 ≤ i ≤ n. Thus the classical definition of a code corresponds to the case where S is the full shift. Any code is an S-code but the converse is false as shown with the following example.

Example 2. The set {a, ab, ba} is not a code but it is not difficult to see that it is an S-code in the even system. Indeed any word with two factorizations contains the block aba.

Let S be a sofic shift. A set X on the alphabet A is said to be complete in S, or S-complete, if X is an S-code and any word in Fact(S) is a factor of a word in X * . For instance the code X = {a, bb} is complete in the even system.

An S-code X is maximal if it is not strictly included in another S-code.

In [START_REF] Reutenauer | Ensembles libres de chemins dans un graphe[END_REF] is an example of an S-complete code which is not maximal. Indeed, let us consider the shift of finite type S defined on the alphabet A = {a, b} and avoiding the blocks aa and bb. The S-code X = {ab} is S-complete but not maximal since X is strictly included in the S-code Y = {ab, ba}.

There is a connection between complete S-codes and a concept which has been studied in symbolic dynamics. This explains why the results proved in Section 4 are related with the results of Williams [START_REF] Williams | Lattice invariants for sofic shifts[END_REF] and Nasu [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts[END_REF]. Let X be a complete S-code. Let A = (Q, E) be the Fischer cover of S. We build an automaton B computed from X and A as follows. The set of states of B contains the set of states Q of A. For each path in A labeled by a word in X going from a state p to a state q, we build a path in B from p to q with dummy states inbetween. Let T be the subshift of finite type made of the bi-infinite paths of the graph of B. The labelling of the paths in the automaton B defines a block map φ from T to S. The set X is an S-code if and only if φ is finite-to-one. It is S-complete if and only if φ is onto. Thus statements on complete S-codes can be reformulated as statements on finite-to-one factor maps between irreducible sofic shifts.

Completion of an S-Code

The following result generalizes the theorem of Ehrenfeucht and Rozenberg [START_REF] Ehrenfeucht | Each regular code is included in a maximal regular code[END_REF]. As in the case of the extension to subshifts of finite type obtained in [START_REF] Ashley | Surjective extensions of sliding-block codes[END_REF], the proof uses the same type of construction as the one of [START_REF] Ehrenfeucht | Each regular code is included in a maximal regular code[END_REF]. It requires however, as we shall see, a careful adaptation to extend to sofic shifts.

Theorem 1. Let S be an irreducible sofic shift. If X is an S-code, there is an S-code Y such that X ⊆ Y and Y is S-complete. If X is moreover regular, Y can be chosen regular and is computable in an effective way.

A nonempty word w of A * is called unbordered if no proper nonempty left factor of w is a right factor of w. In other words, w is unbordered if and only if w ∈ uA + ∩ A + u implies u = ε, where ε denotes the empty word.

The following lemma provides the construction of an unbordered word in the set of factors of an irreducible sofic shift. It replaces the construction used in [5, Proposition 3.6] for the case of the full shift. Lemma 1. Let S be an irreducible sofic shift which has a positive entropy. Let z be a word in Fact(S). Then there is a word y in Fact(S) such that z is a factor of y and y is unbordered.

Proof. Let A be the Fischer cover of S. Let m be the number of states of A and let k be the length of z. Since S has a positive entropy, there are two distinct nonempty words u, v labels of first return paths in A to state p. The words u and v are not two powers a same word since A is deterministic. Moreover {u, v} * is a submonoid of Fact(S). Let w = u k+m v k+m . Since k + m ≥ 2, by [ We claim that y is unbordered. This fact is trivial by considering the length, greater than 2k + 2m, of w ′ , the length k + 2m of b 1 zb 2 and the fact that w ′ is unbordered.

Proof (Sketch of proof of Theorem 1). Let S be an irreducible sofic shift. We denote by A the Fischer cover of S. Let X be an S-code.

Let us suppose that X is not S-complete. Consequently there is a word z in Fact(S) which is not in Fact(X * ).

We first assume that S has a null entropy. This means that the Fischer cover A is made of a unique cycle. One can assume that there is a state p such that p has no outgoing path in A labeled in X. Otherwise X is already S-complete. Since A is irreducible, one can assume without loss of generality that z is the label of a path in A going from a state p to itself, and that z is moreover a synchronizing word of A. We set Y = X ∪ {z}. Now we show that Y is an S-code. Assume the contrary and consider a relation

x 1 x 2 . . . x n = y 1 y 2 . . . y m ,
with x 1 x 2 . . . x n ∈ Fact(S), x i , y j ∈ Y , and x n = y m . The set X being an Scode, at least one of the words x i , y j must be z. Hence, for instance x 1 x 2 . . . x n = x 1 x 2 . . . x r zx r+1 . . . x n . The word zx r+1 . . . x n is the label of a path in A going through the state p after reading the label z. Since p has no outgoing path in A labeled in X, it follows that x r+1 . . . x n = z n-r . Hence there is a positive integer k such that x 1 x 2 . . . x n = x 1 x 2 . . . x r z k with x 1 , x 2 , . . . , x r = z. Since z is not a factor of X * , there is also a positive integer l such that y 1 y 2 . . . y m = y 1 y 2 . . . y t z l with y 1 , y 2 , . . . , y t = z. The above relation becomes

x 1 x 2 . . . x r z k = y 1 y 2 . . . y t z l , which contradicts the hypothesis that x n = y m since z / ∈ Fact(X * ). It is trivial that Y is S-complete.
We may now assume that S has a positive entropy. Without loss of generality, by extending z on the right, one can moreover assume that z is a synchronizing word. By Lemma 1, we construct a word y ∈ Fact(S) which is unbordered and has z as factor. Moreover y is a synchronizing word of A.

If L is a language of finite words, we denote by u -1 L (resp. Lu -1 ) the set of words z such that uz ∈ L (resp. zu ∈ L).

We define the sets U and Y by

U = y -1 Fact(S)y -1 -X * -A * yA * , (1)
Y = X ∪ y(U y) * . (2)
The rest of the proof consists in verifying the following three properties.

-The set Y is a subset of Fact(S).

-The set Y is an S-code.

-The set Y is S-complete.

It is clear from Equations ( 1) and ( 2) that Y is regular when X is regular. It can be computed in an effective way from these equations.

⊓ ⊔ Remark 1. Note that our proof shows that, if S is an irreducible sofic shift with a positive entropy, and X is a code, then X can be completed into a code Y (i.e a code for the full shift) which is S-complete. We do not know whether this property also holds for irreducible shifs of entropy zero.

In [START_REF] Restivo | Codes with constraints[END_REF][START_REF] Restivo | Codes and local constraints[END_REF] (see also [START_REF] Ashley | Surjective extensions of sliding-block codes[END_REF]), it is proved that if S is an irreducible shift of finite type and X a code with X * ⊆ Fact(S) which is not S-complete, X can be embedded into an S-complete set which is moreover a code (i.e a code for the full shift). The proof of our theorem allows us to recover this result. Indeed, when X * ⊆ Fact(S), our construction build an S-code Y which is a code. Moreover, the S-complete code Y that we have built satisfies also Y * ⊆ Fact(S), when X * ⊆ Fact(S). This is due to the strong synchronization properties of the Fischer cover of an irreducible shift of finite type.

Example 3. We consider the even system S of Example 1 on the alphabet A = {a, b}. Let X = {a, ba}. The set X is an S-code but it is not S-complete since for instance z = bb does not belong to Fact(X * ). The regular completion of X is obtained following the proof of Theorem 1. We replace z by bba in order to get a synchronizing word. The proof of Lemma 1 says that the word a 2 b 4 bbaa 2 b 4 is an unbordered word of Fact(S). But a smaller y can be chosen. For instance y = bba also is an unbordered word of Fact(S). We then define U and Y as in Equations ( 1) and [START_REF] Reutenauer | Ensembles libres de chemins dans un graphe[END_REF]. The set Y is a regular S-complete code.

We derive the following corollary which generalizes to codes in irreducible sofic shifts the fact that any maximal code is complete [START_REF] Berstel | Theory of codes[END_REF]Theorem 5.1].

Corollary 1. Let S be an irreducible sofic shift. Any maximal S-code is Scomplete.

Polynomial of a Code

In the sequel, S is an irreducible sofic shift recognized by its Fischer cover A = (Q, E). Let µ A (or µ) be the morphism from A * into N Q×Q defined as follows.

For each word u, the matrix µ(u) is defined by

µ(u) pq = 1 if p • u = q 0 otherwise.
The matrix α A (u) (or α(u)) is defined by α(u) = µ(u)u. Thus the matrix α(u) is obtained from µ(u) by replacing its coefficients 1 by the word u. The coefficients of α(u) are either 0 or u. In this way α is a morphism from A * into the monoid of matrices with elements in the set of subsets of A * . The morphism α is extended to subsets of A * by linearity. For a finite set X, we denote by p X the polynomial in commuting variables:

p X = det(I -α(X)).
The following result is proved in [START_REF] Béal | Codes and sofic constraints[END_REF]. It is a generalization of a result of C. Reutenauer [START_REF] Reutenauer | Ensembles libres de chemins dans un graphe[END_REF] who has proved it under more restrictive assumptions.

Theorem 2. Let S be an irreducible sofic shift and let X be a finite complete S-code. The polynomial p A divides p X .

Example 4. For the even shift and the set X = {aa, ab, ba, bb}, we have

α(A) = a b b 0 and α(X) = aa + bb ab ba bb ,
and

p A = 1 -a -bb, p X = 1 -aa -2bb + b 4 = (1 + a -bb)(1 -a -bb).
We present here two combinatorial proofs of this result, which come as an alternative to the analytic proof presented in [START_REF] Béal | Codes and sofic constraints[END_REF]. Both proofs rely on the reduction of automata with multiplicities.

The first proof goes along the same line as the proof of a result of S. Williams presented in Kitchen's book [12, p. 156], giving a necessary condition to the existence of a finite-to-one factor map between irreducible sofic shifts.

We first build as in Section 2 an automaton B computed from X and A as follows. The set of states of B contains the set of states Q of A. For each path in A labeled by a word in X going from state p to state q, we build a path in B from p to q with dummy states inbetween as shown in Example 5. The automaton B is unambiguous if and only if the set X is an S-code. It represents S if and only if the set X is S-complete.

Example 5. Consider the code X = {aa, ab, ba, bb} in the even system S. The automaton B is represented in the right part of Figure 2. Since X is a complete S-code, B is unambiguous and represents S. Without loss of generality, one can assume that B is irreducible. Otherwise, one keeps only a strongly connected component of B representing S. By construction, p A = det(Iα A (A)) and p X = det(Iα B (A)).

Hence, Theorem 2 is a consequence of the following result.

Proposition 1. Let S be an irreducible sofic shift and let A be its Fischer cover. If B is an unambiguous and irreducible automaton representing S, det(I-α A (A)) divides det(Iα B (A)).

Proof (Sketch of proof ). The degree of a word u in an automaton is defined as the number of paths labeled by u. The degree of an automaton is the minimal non-null value of the degree of words. Any unambiguous irreducible automaton of degree k has the following property: for any word u of degree k and any word w such that uwu has a non-null degree, uwu has degree k.

We first assume that the Fischer cover A of S is codeterministic (or left resolving): for any state p ∈ Q and any word u, there is at most one path labeled by u and ending at p. In this case the degree of A is d = 1. Indeed, since A is a Fischer cover, it has a synchronizing word. Since A is codeterministic, each synchronizing word has degree 1.

Let v (resp. w) be a word which has a non-null and minimal degree k (resp. d = 1) in B (resp. in A). Since B is irreducible, there are words z, z ′ such that vzwz ′ v has a non-null degree. Hence vzwz ′ v has degree k in B and degree d = 1 in A. We set u = vzwz ′ v.

An N-automaton with a set of states Q is a triple I, µ, T , where I and T are two vectors -respectively initial row vector and final column vector -with entries in N, and where µ is a morphism from A * into N Q×Q . It is equivalently defined by the triple I, α(A), T . Two N-automata I, µ, T and J, µ ′ , F are equivalent if and only if, for any word w ∈ A * , Iµ(w)T = Jµ ′ (w)F .

Let 1 A be the row-vector with all coefficients equal to 1 of size the number of states of A, and 1 t A its transpose. It follows from the definition of the word u that the two N-automata C = k1 A µ A (u), µ A , µ A (u)1 t A , and D = d1 B µ B (u), µ B , µ B (u)1 t B , are equivalent. The standard Schützenberger reductions of the N-automata C and D over the field R are similar. The reduction of each N-automaton is obtained through a left reduction followed by a right reduction (see for instance [START_REF] Berstel | Rational series and their languages[END_REF] or [START_REF] Sakarovitch | Éléments de Théorie des Automates[END_REF]).

Since u has degree 1, the initial row (resp. final column) vector of C has a unique non-null coefficient. Consequently, since A is deterministic (resp. codeterministic) and irreducible, the automaton C is left (resp. right) reduced. Hence C is already reduced.

Finally, one can prove that the transition matrix of D is similar to a matrix having a principal subblock equal to the transition matrix of its left (or right) reduced form. It follows that det(Iα A (A)) divides det(Iα B (A)). The extension to sofic shifts that may not have a codeterministic Fischer cover can be obtained with a specialization argument (see [START_REF] Béal | Codes and sofic constraints[END_REF]).

⊓ ⊔ Example 6. We continue with Example 5. The word bab has degree 2 in B and 1 in A. Hence the N-automata can be now reduced on the left side. We get that G is similar to H. The upper left block matrix of size 2 of G is similar to α A (A). As a consequence, det(Iα A (A)) = 1abb divides det(I -H) which divides det(I -F ) = det(Iα B (A)) = (1abb)(1 + abb).

C = ˆ0 2 ˜, µA(A) = » a b b 0 - , » 0
A variant of the combinatorial proof uses an argument due to Nasu [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts[END_REF]. We denote by M (resp. M ′ ) the matrix M = a∈A µ A (a) and (resp. M ′ = a∈A µ B (a)). It is known from the Perron-Frobenius theory that M and M ′ have the same positive spectral radius λ, the logarithm of λ being called the topogical entropy of the sofic shift S [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]. Let U , V (resp. U ′ , V ′ ) be two real positive left and right eigenvectors of M (resp. of M ′ ) for the eigenvalue λ. One can choose these vectors such that U V = U ′ V ′ = 1. With these settings, the two R-automata C = U, µ A , V and D = U ′ , µ B , V ′ are equivalent.

The proof of this equivalence relies on the following arguments. One first divides µ A and µ B by λ to assume that λ = 1.

For any word x ∈ A * and any R-automaton S = I, µ, T , we denote by π S (x) the real coefficient Iµ(x)T . Hence C and D are equivalent if and only if π C (x) = π D (x) for any x ∈ A * . The functions π C and π D define two rational probability measures on A * [START_REF] Hansel | Mesures de probabilités rationnelles[END_REF]. These measures satisfy the following properties.

-A right (and left) invariance property: for any x ∈ A * , with S equal to C or D. Moreover, since the automata A and B are unambiguous, one can show that there are positive real numbers ρ, ρ ′ such that for any x ∈ A * , π C (x) ≤ ρ π D (x) and π D (x) ≤ ρ ′ π C (x). The equivalence of C and D follows from these inequalities. The reduction of the automata is used to finish the proof as before.

Fig. 1 .

 1 Fig.1. The Fischer covers of the even system S on the left, and of the golden mean system T on the right.

  10, Theorem 9.2.4 pp. 166], w is a primitive word. It follows that the Lyndon word w ′ conjugate to w is unbordered (see for instance [10, Proposition 5.1.2 p. 65]). Since A is irreducible, there are two words b 1 , b 2 of length at most m such that the word y = w ′ b 1 zb 2 w ′ ∈ Fact(S).

Fig. 2 .

 2 Fig. 2. The automaton A (on the left), and the automaton B computed from A and X = {aa, ab, ba, bb} (on the right).

1 - 5 .

 15 , and D = ˆ0 1 0 0 0 1 0 ˜, µB(A), ˆ0 1 0 0 0 1 0 ˜t , are equivalent. We obtain a right-reduction of the automaton D = I, E = α B (A), T by computing a basis of the vector space generated by the vectors in µ(A * )T . We can choose the basis (T, µ(b)T, µ(ab)T ) since µ(a)T = 0, µ(bb)T = T , µ(bab)T = T and µ(aab)T = µ(ab)T . This basis is extended to a basis of R 7 , for instance with the first 4 column vectors e 1 , . . . e 4 of the canonical basis of R 7 . Let F and H be the matrices We get that E is similar to F . Let us denote by G the upper left block matrix of size 3 of F . The right-reduced automaton 2 0 0 , G =

-

  w∈A k π S (xw) = π S (x). An ergodic property: for any x ∈ A * , with S equal to C or D. π S (xwy) = π S (x)π S (y).

Acknowledgments The authors would like to thank an anonymous reviewer for detecting an error in Lemma 1 in a preliminary version of this paper.