P H Gosselin
email: gosselin@ensea.fr

F Precioso

S Philipp-Foliguet

Incremental Kernel Learning for Active Image Retrieval without Global Dictionaries

Keywords: Multimedia retrieval, Interactive retrieval, Visual dictionaries, Machine learning, Kernel function

In content-based image retrieval context, a classic strategy consists in computing off-line a dictionary of visual features. This visual dictionary is then used to provide a new representation of the data which should ease any task of classification or retrieval. This strategy, based on past research works in text retrieval, is suitable for the context of batch learning, when a large training set can be built either by using a strong prior knowledge of data semantics (like for textual data) or with an expensive off-line pre-computation. Such an approach has major drawbacks in the context of interactive retrieval, where the user iteratively builds the training data set in a semi-supervised approach by providing positive and negative annotations to the system in the relevance feedback loop. The training set is thus built for each retrieval session without any prior knowledge about the concepts of interest for this session. We propose a completely different approach to build the dictionary on-line from features extracted in relevant images. We design the corresponding kernel function, which is learnt during the retrieval session. For each new label, the kernel function is updated with a complexity linear with respect to the size of the database. We propose an efficient active learning strategy for the weakly supervised retrieval method developed in this paper. Moreover this framework allows the combination of features of different types. Experiments are carried out on standard databases, and show that a small dictionary can be dynamically extracted from the features with better performances than a global one.

Introduction

Kernel-based methods for multimedia retrieval have shown their robustness for many tasks, in shape recognition [START_REF] Sahbi | Kernel PCA for similarity invariant shape recognition[END_REF], image retrieval [START_REF] Gosselin | Combining visual dictionary, kernel-based similarity and learning strategy for image category retrieval[END_REF], or event detection [START_REF] Nasser | The use of kernel methods for audio events detection[END_REF] for instance. Most methods first build a kernel function, usually from supervised data [START_REF] Chen | Image categorization by learning and reasoning with regions[END_REF], then train a classifier such as Support Vector Machines (SVM). This procedure is relevant in the context of batch learning, when a large training set is provided. However, in the context of interactive retrieval, building an initial kernel before any retrieval session is a difficult task, since there is no initial training set. Indeed, in this specific context, the training set is iteratively built through interactions with the user who provides labels on unknown data. A classic strategy is to consider highly discriminant kernel functions, such as thin Gaussian kernels, which give the classifier the ability to shatter the database. The main drawback of such a strategy is the weak generalization capacity of the retrieval system.

The other solution we want to explore in this paper is to build the kernel function during the retrieval session and thus to adapt it to the current training set.

The framework proposed in this paper is general, but we will give applications for global descriptions of data using histograms. We will give examples of kernel designs for these histograms.

A common process when dealing with histograms is to first build a dictionary of visual words on a training set, using clustering methods, such as K-means [START_REF] Grauman | The pyramid match kernel : Discriminative classification with sets of image features[END_REF] or randomized forests [START_REF] Moosmann | Randomized clustering forests for image classification[END_REF]. Each data in the database is then represented by a histogram on this visual dictionary. Then, a kernel function, RBF or Fisher kernel, is considered. Such strategies proved to be very powerful in a batch learning context, when a large training set is available [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF][START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF]. In [START_REF] Perronnin | Universal and adapted vocabularies for generic visual categorization[END_REF], Perronnin first proposed to build two kinds of visual dictionaries per category: one "universal" visual dictionary is build on the whole database with a Gaussian mixture model (GMM) without any supervision, while the other one dedicated to the category uses labelled training data to learn the GMM of that category. In [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF], Perronnin et al. applied Fisher kernel on visual words modeled with a combination of "universal" and "categorical" GMMs, restricted to diagonal variance matrices for each component of the mixture. Deriving a diagonal approximation of the Fisher matrix of a GMM, they obtain a (2d + 1) × k -1 dimensional vector representation of an image feature set, or d × k dimensional vector when considering only the components associated with either the means or the variances of the GMM. In a very recent work [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF], Perronnin et al. further improved the Fisher kernel in several ways. Inspired by these works, [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] Jegou et al. proposed a simpler approach in which a K-Means algorithm and a new descriptor aggregation approximate the universal GMM. This last method is a good approximation of Perronnin et al. sophisticated GMM models and produces comparable results.

However, in our context of interactive retrieval, we have very few assumptions both on the concepts the user is looking for and on the database which is completely unknown at the beginning. Hence, using a single dictionary computed for all concepts does not seem judicious, since concepts themselves are unknown.

A solution could be to compute a new dictionary based on the features from the images labelled by the user, at each feedback loop. One could, for example, consider very recent work of Mairal et al. [START_REF] Mairal | Online dictionary learning for sparse coding[END_REF] which iteratively builds a dictionary using on-line techniques in order to speed up the dictionary computation. However, this method is not adapted to the active learning context since all the histograms must be recomputed at each iteration with the new dictionary, and thus there is no strategy for selecting the optimal samples for annotation.

Another idea could be to incrementally design a kernel function directly on training data from base kernels (seen as weak-learners), using the boosting paradigm as in Crammer et al. approach [START_REF] Crammer | Kernel design using boosting[END_REF]. However, as in the classic boosting algorithm [START_REF] Schapire | The strength of weak learnability[END_REF], in order to determine penalties and weights involved in boosted kernel construction at each iteration, the current kernel has to be evaluated on all previously labelled data from the training set. The computation time of this evaluation increases along the interactive learning process and that is what we want to avoid.

In this paper we propose a general framework for interactive image retrieval with three main contributions. First we give a way to dynamically build the dictionary from visual words extracted from labelled images. Secondly we incrementally build the kernel function from the visual words added at each feedback step. The resulting kernel is the same as the one computed from scratch, except that the computational complexity is linear with respect to the size of the database. Thirdly, as this incremental kernel learning method allows an efficient active learning strategy, we propose a function which selects the images that contain the most interesting features. Section 2 gathers the works related to the three contributions, which are themselves presented in section 3. In section 4 we present an application of the method using low-level features such as color or texture vectors. Finally, in sections 5 and 6, we present experimental results carried out on generalist databases. These results show that the proposed method performs better than the classic one where a global dictionary is used, even if the global dictionary is optimally tuned.

RELATED WORK

Iterative dictionary building

Our aim is to provide an algorithm able to build a single dictionary adapted to active learning, that is to say, able to be the most generative regarding the class the user wants to retrieve but also the most discriminative to all other possible classes. Furthermore, since we are considering active learning framework, our dictionary learning has to be fast and compliant with weakly-supervised context.

Dictionary learning algorithms received recently a lot of consideration mainly due to the increase of dataset size in classification context. If the interest is mainly focused on second-order iterative batch approaches for their computational speed compared to first order gradient descent methods [START_REF] Lee | Efficient sparse coding algorithms[END_REF], such methods cannot deal with very large training sets since the whole training set is required at each iteration to minimize the empirical risk (or more usually a surrogate function of this risk) [START_REF] Bottou | The tradeoffs of large scale learning[END_REF]. In [START_REF] Mairal | Supervised dictionary learning[END_REF], the authors introduce a discriminative approach to supervised dictionary learning that effectively exploits the corresponding sparse signal decompositions in image classification tasks, and propose an effective method for learning a shared dictionary. The key idea is to learn simultaneously a single shared dictionary and models for different signal classes in a mixed generative and discriminative formulation.

A recent approach [START_REF] Mairal | Online dictionary learning for sparse coding[END_REF] has been proposed to iteratively build a dictionary by processing one element (or a small subset) of the training set at a time. As mentioned by the authors: such online approach "is particularly important in the context of image and video processing [START_REF] Protter | Image sequence denoising via sparse and redundant representations[END_REF], where it is common to learn dictionaries adapted to small patches, with training data that may include several millions of these patches (roughly one per pixel and per frame)".

However, Mairal et al. [START_REF] Mairal | Online dictionary learning for sparse coding[END_REF] approach suffers from excessive computational cost regarding active learning requirements. Indeed, during the dictionary update steps, the new dictionary D t is computed by minimizing a surrogate cost function of the empirical cost function (under some constraints) using both the new annotated data x t and its decomposition α t over the dictionary D t-1 obtained at the previous iteration. These dictionary update steps can be speeded up using D t-1 as a warm restart to compute D t . However, classical sparse coding steps require to compute the decomposition α i of x i over the dictionary D i-1 and thus the minimization (computed by LARS algorithm) on all possible α values in R k :

α i argmin α∈R k 1 2 x i -D i-1 α 2 + λ α 1
where λ ∈ R is a regularization parameter. Such computation is definitely not suitable to our context, where we target quasi real-time response from the system. Both the dictionary update and the sparse decomposition of the data over the dictionary have to be real-time compliant.

Kernel learning

In this paper, we focus on kernel-based learning techniques. The main motivation is that, once one has a kernel function, a lot of powerful learning methods can be used. This is also a good framework for reasoning and creating new methods. More specifically, we are interested in methods for learning kernels.

A first class of methods related to this task is distance learning techniques (which respects the triangle inequality), since kernels are easily built from distances. Such methods have been proposed for learning Mahalanobis distances:

d(x, x ′ ) 2 = r (x r -x ′ r ) ⊤ A(x r -x ′ r ) (1)
with x and x ′ image indexes and A 0 a positive semi-definite matrix, that can be learnt using optimization [START_REF] Xing | Distance metric learning, with application to clustering with side-information[END_REF][START_REF] Davis | Informationtheoretic metric learning[END_REF][START_REF] Lee | Rank-based distance metric learning: an application to image retrieval[END_REF] or boosting [START_REF] Hertz | Learning distance functions for image retrieval[END_REF]. The method in [START_REF] Davis | Informationtheoretic metric learning[END_REF] is interesting for our context, since the algorithm seems to be able to update matrix A for each new label. All values of matrix A are subject to change, and thus all distance values between labelled and labelled/unlabelled images must be recomputed.

A second class of methods learns a combination of kernel functions (a.k.a. multiple kernel learning), for instance using optimization [START_REF] Lanckriet | Learning the kernel matrix with semi-definite programming[END_REF][START_REF] Bach | High-dimensional non-linear variable selection through hierarchical kernel learning[END_REF][START_REF] Joutou | A food image recognition system with multiple kernel learning[END_REF]. In most cases, a linear combination of minor kernels is performed:

K(x, x ′ ) = j β j k j (x, x ′ ) (2)
Weights β j are computed according to the current labels, and to unlabelled data for semi-supervised algorithms. In many cases, the computation of weights β j can be performed with complexity at most linear with the database size. All weights β j are subject to change, and all kernel values between labelled and labelled/unlabelled images must be recomputed.

A third class of methods performs the learning of the Gram matrix G ij = K(x i , x j ), for instance using boosting [START_REF] Crammer | Kernel design using boosting[END_REF] or optimization [START_REF] Bach | High-dimensional non-linear variable selection through hierarchical kernel learning[END_REF]. With such methods, like the method we propose in section 3, we work on the row r j = (G ij ) i of the Gram matrix which corresponds to the labelled images or on an approximation with eigen decomposition. That means that these methods directly produce the kernel values we are interested in. The method in [START_REF] Crammer | Kernel design using boosting[END_REF] proposes a boosting algorithm for learning a linear combination of Gram matrices. This method is interesting since it creates weak hypothesis on the fly, during boosting rounds, which is similar to our aim of building a dictionary (and hence new indexes) during retrieval. However, all boosting rounds need to be run again at each feedback step.

Most of the kernel learning methods we presented in this section are able to learn new parameters for kernel building in reasonable time for our context, sometimes thanks to some modifications/approximations. Next to that an update of distance/kernel values must be performed with complexity O(m × n), with m the number of labelled images and n the number of images in the database. To the best of our knowledge, there is no method to perform these operations with a lower complexity. Furthermore, most of these methods do not directly deal with dynamic indexes, and thus full re-computations are required when indexes are changed, contrary to the method we propose in section 3.

Active learning

Many strategies have been proposed to select the best image to be labelled as positive or negative. They are usually described as "pessimistic" methods, "optimistic" methods, or as a combination of both.

"Pessimistic" methods will not necessarily lead to the fastest increase of performance at each feedback iteration, but they take a minimal risk. They ensure that a minimal performance is reached after a given number of labels. The most common technique of this class consists in selecting the documents the closest to the classifier boundary [START_REF] Cohn | Improving generalization with active learning[END_REF]. This strategy is used for instance with SVM [START_REF] Tong | Support vector machine active learning with application to text classification[END_REF], kNN [START_REF] Jain | Active learning for large multi-class problems[END_REF] and boosting [START_REF] Li | Improving adaboost for classification on small training sample sets with active learning[END_REF][START_REF] Collins | Towards scalable dataset construction: An active learning approach[END_REF], with extensions to deal with multiple image selection [START_REF] Brinker | Incorporating diversity in active learning with support vector machines[END_REF][START_REF] Hoi | Semi-supervised SVM batch mode active learning with applications to image retrieval[END_REF] and with multi-label learning [START_REF] Vijayanarasimhan | What's it going to cost you?: Predicting effort vs. informativeness for multi-label image annotations[END_REF][START_REF] Zhang | Interactive localized content based image retrieval with multiple-instance active learning[END_REF]. It has been proven that selecting the most uncertain images is asymptotically the fastest strategy for dividing Version Space in the case of SVM [START_REF] Tong | Support vector machine active learning with application to text classification[END_REF] and boosting [START_REF] Li | Improving adaboost for classification on small training sample sets with active learning[END_REF]. This strategy is optimal if one can select a document on the classifier boundary, but usually there is no document right on the boundary, and the constraint is relaxed by choosing a document near the boundary. The selection criterion can be the distance to the boundary [START_REF] Tong | Support vector machine active learning with application to text classification[END_REF], the entropy/probability [START_REF] Jain | Active learning for large multi-class problems[END_REF], or samples where several classifiers agree/disagree [START_REF] Cheng | Active learning for image retrieval with co-SVM[END_REF]. That means that the theoretical optimum is never reached, but this strategy is still able to very well identify areas containing the most interesting documents to label, even if there are few labels (about 20-40) [START_REF] Tong | Support vector machine active learning with application to text classification[END_REF][START_REF] Li | Improving adaboost for classification on small training sample sets with active learning[END_REF]. Methods have been proposed to deal with the case of very few labels (2 or more) [START_REF] Gosselin | Active learning methods for interactive image retrieval[END_REF].

"Optimistic" active learning methods can lead to the fastest increase of performance, but they do not ensure that a minimal performance is reached after a given number of labels. Criteria of selection can be the minimization of expected classification error [START_REF] Roy | Toward optimal active learning through sampling estimation of error reduction[END_REF], the maximization of mutual information about the labels of the unlabelled documents [START_REF] Guo | Optimistic active learning using mutual information[END_REF], or the maximization of expected average precision [START_REF] Gosselin | Active learning methods for interactive image retrieval[END_REF]. The main drawback of these methods is that an unexpected label can lead to no improvement. For instance, let us consider the selection of an image that, once labelled as positive, would enhance a lot the retrieval. If the user labels this image as positive, the classification is much improved, whereas if it is labelled as negative, there is no improvement. Since the efficiency of these methods depends on all previous labels, the latter case may happen more frequently when there are very few labels.

Considering advantages and drawbacks of these two classes of active learning methods, the combination of them is interesting [START_REF] Gosselin | Active learning methods for interactive image retrieval[END_REF]. Uncertainty-based methods perform well when selecting the interesting areas of document space. Hence, one can preselect the images the closest to the classifier boundary. Selecting within these preselected images (thanks to an uncertainty criterion) is subject to the inaccuracy of classifier boundary, especially with few labels. Then, an optimistic strategy can be used to select within the preselected images. When using such a combination of strategies, highly promising images can be selected, while ensuring a minimal improvement.

PROPOSED FRAMEWORK

In this section, we present the general framework to build a dictionary of visual words and to learn a kernel function simultaneously during a retrieval session. In Fig. 1(a) we present a classic learning scheme for interactive retrieval. It is composed of two main stages: off-line and on-line stages. The off-line stage is performed once and only once before any retrieval session. During this stage, features are first extracted from images (in the example, colours). Then a dictionary of features is computed, generally using K-Means. Since there is no label, the usual criterion for word computation is the distortion (or equivalent), which aims at minimizing the difference between a feature and its corresponding word. Then, features are projected onto the dictionary in order to get indexes, such as histograms. The on-line stage is performed each time a new retrieval session begins. Retrieval session is initialized with some images of the category (in the example of Fig. 1, a single image of bicycle), an the database is classified according to these first labels. Then the active learner selects unlabelled images that, once labelled, will enhance the most the classification of the database. The user labels these images, which are added to the current training set. These steps are repeated until the user is satisfied or tired.

In Fig. 1(b) we present the learning scheme we propose to use in this paper. The main difference is that we move all the processes related to the dictionary from the off-line stage to the on-line stage. Such a change allows to perform the dictionary computation with the information brought by user labels. Even if we have very few labels in the interactive retrieval, this information can still slightly improve the relevance of the dictionary for the currently searched category. Of course, as we focus on real time image retrieval, full re-computation of indexes is not an acceptable solution. In our case, we use kernels for classification, and hence we only compute what is required to update the previous kernel to the new one.

Dynamic dictionary

In this section, we assume that each image i is represented by a set P i = {p ri } r of features p ri in feature space P. For instance, P i can be the set of the most representative color vectors of image i. These features are precomputed for all images of the database, or computed on the fly for query images outside the database.

The first aim of the method is to build dictionary D L = {p l } l∈[1,L] of features pl , but with the constraint that they are features from images of the database. We call words the features selected to enter the dictionary. The first advantage of such a strategy is that all possible words (and latter minor kernels) are known before any retrieval session, and thus allow the use of cache algorithms to save computational time.

At the beginning of a retrieval session, the dictionary D 0 is empty. Then, at each feedback step, we add to the dictionary features from images labelled as positive. They are added as soon as they are different from the ones already in the dictionary. As we will see with experiments, positive labelled images seem to contain most of the interesting features.

We denote g D (p) a feature selection function which returns 1 if feature p can be added to dictionary D, and 0 otherwise. Examples of such functions are presented in section 4.

Incremental kernel learning

For each new word pl , we build a minor kernel function k pl (P i , P j ), which is the similarity between image i and image j relatively to pl . We sum all these minor kernels to get the kernel according to current dictionary D L :

K L (P i , P j ) = L l=1 k pl (P i , P j ) (3)
with L the number of words in dictionary D L .

The incremental computation of this kernel is straightforward:

K L+1 (P i , P j ) = K L (P i , P j ) + k pL+1 (P i , P j ) (4)
If P is the space of feature sets, minor kernels k pl (P i , P j ) are computed using evaluation function e pl : P → R defined for feature pl and similarity function δ by : k pl (P i , P j ) = δ(e pl (P i ), e pl (P j ))

The simplest evaluation function e pl equals 1 if pl is in P i and 0 otherwise. This formula can be used for dictionary of visual words, where one only checks whether keyword pl belongs to image P i . In the case where an image is represented by a set of colours, e pl (P i ) can return the number of pixels whose color is close to pl .

The similarity function δ compares the evaluation of images i and j regarding feature pl . This function must be chosen so that the expansion of function K L in Eq. ( 3) is a kernel function. Thus function e pl does not need to satisfy any mathematical property to lead to a kernel function.

Active learning strategy

In this section, we present a method to perform active learning within our kernel learning framework. We denote by y = (y i ) i the label vector, with y i ∈ {-1, 0, 1} the label of image i (1 for relevant images, -1 for irrelevant images, and 0 when there is no label).

Active learning aims at selecting the unlabelled images which, once labelled by the user and thus added to the training set, will improve at most the classifier. This can be expressed as the minimization of a function a(i) over unlabelled images :

i ⋆ = argmin {i|y i =0} a(i) (6)
i ⋆ is the index of the selected image. A common active learning function selects the images the closest to the classifier boundary. When the classifier is SVM, a(i) can be the distance of image i to the separating hyperplane. In this case, we have the SV M active method proposed by Tong [START_REF] Tong | Support vector machine active learning with application to text classification[END_REF].

Because of the inaccuracy of the classifier boundary with very few labels, we apply a correction using the method in [START_REF] Gosselin | Active learning methods for interactive image retrieval[END_REF]. Then, we preselect the 100 images the closest to this corrected boundary. The selection within these 100 images uses the following active learning method.

For each feature p in unlabelled images, we compute the kernel target alignment between the labels and the kernel k p (cf. Eq. ( 5)). This criterion, proposed by Cristianini [START_REF] Cristianini | On kernel target alignement[END_REF], is a measure of similarity between a kernel and a set of labels. The higher the alignment is, the higher the kernel k p "fits" the category represented by the labels y:

A y (k p ) = k p , yy ⊤ k p , k p yy ⊤ , yy ⊤ (7)
with ., . the dot product. Since labels do not change during active learning selection, the active selection function can be written as:

a(t) = argmin p ∈ P t g D (p) = 1
i j y i y j δ (e p (P i ), e p (P j )) i j δ (e p (P i ), e p (P j )) [START_REF] Collins | Towards scalable dataset construction: An active learning approach[END_REF] with g D (p) a feature selection function which returns 1 if feature p can be added to dictionary D, and 0 otherwise (see section 4.1).

Bound the dictionary

In order to save memory, we propose a method to bound the size of the dictionary. The main idea is to compute the kernel target alignment for each word pl of the dictionary, and only to use the words that maximize the alignment.

Considering the kernel target alignment computation time, since we have very few labels, their re-computation is not a problem. For enabling a word, the update is the same as before (cf. Eq. ( 4)). For disabling a word pl , the update is the following:

K L+1 (P i , P j ) = K L (P i , P j ) -k pL+1 (P i , P j ) (9)
At the end of the section 5.2.2 we present experiments which evaluate the performance according to the maximum number of words in the dictionary.

APPLICATION

In this section, we present an application of the method for dynamic histograms.

Dynamic Histograms

In this application, descriptors are vectors, such as colour or texture. The aim of this application is to iteratively build the kernel function on histograms during the retrieval.

With classic histogram-based features, a dictionary is built for the whole database, before any retrieval session. This is performed using some parametrization, for instance the number of words in the dictionary. As we will show in experiments, performance for each retrieval session depends on this parametrization. With the method we proposed in section 3.1, we get rid of global dictionaries.

Before any retrieval session, we extract and quantize the descriptors within an image using K-Means with Euclidean distance d. In the following experiments, we keep 64 descriptors per image. Then, we build for each image i a set P i of features p ri with:

p ri = (f ri , h ri , θ ri ) ( 10
)
where f ri is the center of cluster r computed by K-Means, h ri the number of vectors in cluster r, and θ ri the distance of f ri to the closest cluster center r ′ = r. These image feature sets P i = {p ri } i are computed off-line. During the on-line retrieval, if D denotes the current dictionary, we only add features from images labelled as relevant if they are not similar to any feature of D. To consider two features p and p as similar, we check if thresholds θ and θ are close enough and if descriptors f and f are close enough according to these thresholds. In this case, the feature selection function g D is:

g D (p) = 1 if ∀p l = ( fl , ĥl , θl ) ∈ D, | θl -θ| θl +θ > 0.8 or d( fl , f ) > θl 0 otherwise (11)
Such a feature selection function can add clusters with similar centers but with different sizes, since parameter θ can be seen as the size of the hypersphere around the cluster center. That means that, for instance, a first center can focus on a very specific blue color, while another one focuses on all blue hues. Then, if the user is looking for a car with a very specific blue color, the first cluster is the most interesting. In another case, if the user is looking for blue skies, the second cluster is the most interesting.

Evaluation value e pl (P i ) of each image P i according to the new word pl first aims at checking if one of the descriptors of image i is close to word pl . In this case, e pl returns the number of descriptors of P i close to pl :

e pl (P i ) = h r ⋆ i if d( fl , f r ⋆ i ) ≤ θl 0 otherwise (12)
with r ⋆ = argmin r d( fl , f ri ).

In the example of color histograms, g W (p) equals 1 if color f is far enough to each color already in D, and x i = (e pl (P i )) l is similar to the histogram of image i regarding dictionary D.

Incremental kernel

We present in this section two similarities δ (cf. Eq. ( 5)) that respectively lead to a triangular and a Gaussian kernel (cf. Eq. ( 3)).

Triangular χ 1 incremental kernel

If the evaluation function always returns positive values, the following function δ can be used, with (x, y) ∈ R 2 :

δ χ 1 (x, y) = - |x -y| x + y ( 13
)
This function is very interesting since it is invariant to scale:

∀α > 0, δ χ 1 (αx, αy) = δ χ 1 (x, y)
Thus, the method is invariant to the magnitudes of evaluation function values. For instance, even if a first evaluation function e pl , corresponding to a first feature pl , returns values around 10 -5 and another one e pk , corresponding to feature pk , returns values around 10 5 , both feature spaces still have the same weight in kernel K L .

This function leads to a triangular kernel with χ 1 distance:

K L (P i , P j ) = L l=1 k pl (P i , P j ) = - δ χ 1 (e pl (P i ), e pl (P j )) = -d χ1 (x i , x j )
with d χ 1 the χ 1 distance between two vectors, and x i = (e pl (P i )) l .

Gaussian L 2 incremental kernel

The method can also be used to incrementally build a Gaussian L 2 kernel, using the following function δ, with (x, y) ∈ R 2 :

δ L 2 (x, y) = - 1 2σ 2 (x -y) 2 (14)
If we compute the exponential value of kernel K L (P i , P j ), we get a Gaussian L 2 kernel: -Label c as positive

K ′ L (P i , P j ) = exp (K L (P i , P j )) = exp l δ L 2 (e pl (P i ), e pl (P j )) = exp - 1 2σ 2 d L 2 (x i , x j ) with d L 2 the L 2 distance
-I ⋆ 0 = s closest images to c in A -Label images of I ⋆ 0 ∩ C

EXPERIMENTS ON INTERACTIVE RETRIEVAL

Evaluation Protocol

We set up an evaluation protocol to estimate the average performance one can expect when starting an interactive retrieval session with a random image. This is performed by the simulation of retrieval sessions for each category, where the user labels the images selected by the active learning technique. A Precision/Recall curve is computed at each feedback step, and then averaged over all retrieval sessions for the same category. Then, the average quality of the ranking is computed with the usual criterion of Average Precision, which is used for example in TRECVID evaluation campaign [START_REF]TREC Video Retrieval Evaluation Campain[END_REF]. At last, in order to have a global quality measure of our system, we compute the Mean Average Precision (MAP) on all categories. Labelling is only performed on the train set, and performance is computed on the test set. Details of the evaluation protocol are shown in Algorithm 1.

Results on VOC2006

We carried out experiments on the VOC 2006 database [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] which contains images belonging to 10 categories. It is split into 1,277 train images and 2,686 test images. Images from this database are shown in Fig. 2. Let us note that we do not follow any of the PASCAL evaluation protocols since we are interested in interactive image retrieval.

We compared two histogram-based methods, one using global dictionaries, and the other one using our dynamically built histogram. In both cases we used L ⋆ a ⋆ b ⋆ colours, textures from quaternion wavelets [START_REF] Chan | Quaternion wavelets for image analysis and processing[END_REF], and SVM to classify the database according to the current labels. Results per category are presented in Table 1 for 10 feedback steps, and results according to each feedback step are presented in Figure 3.

Global dictionary

The first method precomputes a global dictionary with a fixed number of color and texture clusters. We use dictionary sizes of 16, 32, 64, 96, 128, 160, 192, 224 and 256, and consider all combinations of two features with different dictionary sizes. The kernel function is a triangular kernel with χ 1 distance:

K χ 1 (x, y) = - r |x r -y r | x r + y r
The active learning method is the one of [START_REF] Gosselin | Combining visual dictionary, kernel-based similarity and learning strategy for image category retrieval[END_REF]. This is an enhancement of Tong's SVM active method [START_REF] Tong | Support vector machine active learning with application to text classification[END_REF], a reference strategy for interactive retrieval. These two papers compare several interactive retrieval methods and show the large increment brought by active learning strategies.

We display three of the 81 combinations of dictionaries in Table 1 : 64 colours/64 textures, 256 colours/256 textures, and 64 colors/160 textures. The last one is the combination which gives the best overall MAP among the 81 combinations. Performance can be very different from one parametrization to another, for instance for the "bicycle" category, it goes from 32% to 46%. This shows that the performance is highly dependent on the parametrization of the global dictionaries. Fig. 4 shows the average precision for several combinations of dictionary sizes. One can see that results are not regular according to dictionary sizes. This is due to the learning of dictionary: even if we use a K-Means algorithm which gives almost stable dictionaries [START_REF] Patanè | The enhanced LBG algorithm[END_REF], they are still subject to some variations. However, one can see that there is emerging combinations. Let us note that this behaviour is the same for all categories.

Dynamic Histograms

The second method is the one we proposed in section 4.1 with a triangular kernel with χ 1 distance (cf. Eq. 13). Results are shown in the fourth column of Table 1. With this method, no parametrization is needed. On average, our method performs better than the method with global dictionaries, even if global dictionaries are perfectly tuned. That means that, whatever the cross validation performed to optimally tune global dictionaries, performance is better with our dynamic dictionaries.

Let us note that our method is less effective for two categories ("cow"and "sheep"). This can be explained by the fact that these categories can be retrieved with few features (color and texture of grass for instance). That also shows that the method builds discriminative kernels, which is consistent with interactive retrieval, where the user expects to retrieve the images he labelled as positive. That means that the method takes little risk, and selects the features which increase at most the similarity between positive labels and decrease as much as possible the similarity between negative labels. Since only few labels are available for training, in special cases such as "cow"and "sheep"the method does not detect generic features which are relevant for a large category.

We also carried out experiments to evaluate the performance of dynamic dictionaries when their sizes are bounded. The results are shown in Table 2. We tried several maximal numbers of words : 16, 32, 64, 96, and 128. Let us notice that, without bounding, the size of each dictionary goes up to 200 with 51 labels. Results are almost stable for bounding values higher than 96 words, and even with few words, we still have good performance. Fig. 5 shows the average computational time of each feedback step using dynamic dictionaries, when running the system on a single core of an Intel Core 2 Duo with 2GB of memory. The first feedback step is the longest to compute, since all visual words are new, and their evaluation and kernel values need to be computed. For the next feedback steps, only the evaluation and kernel values for the new visual words are computed, the previous values being stored into memory. In order to store these values up to the available memory, we use classic caching algorithms. In order to get average computation time for a single search, we empty caches at the beginning of each retrieval session during these experiments. In the other case, where caches are shared among users, the average time for one feedback step is around 10 milliseconds, the same computational time as for static dictionaries.

Dictionary sizes

Results on Images from the Web

We carried out experiments on the database presented in [START_REF] Schroff | Harvesting Image Databases from the Web[END_REF], which contains images belonging to 18 categories. We only considered non-abstract images labelled as "good" or "ok", which leads to a total of 10610 images. In comparison to VOC2006 images, most images have a poor quality (low resolution and high compression). Some images from this database are presented in Fig. 6. The experimental protocol is the same as the one we used for VOC2006, except that performance is measured on the train set (there is no test and validation sets).

Results are presented in Table 3. Let us first remark that we have lower results than with the previous database and the same features, certainly because of the poor quality of images. We first carried out experiments with global dictionaries of color and textures. We considered all combinations of one color dictionary and one texture dictionary with 64, 128, 256 and 512 words. The first column presents Average Precision using the worst combination, the second one a combination one may choose considering the database size, and the third column the best combination. Again, we observed large differences from one global dictionary tuning to another. It seems that a small color dictionary and a large texture dictionary is the most suited tuning for that database. The last column presents Average Precision using the proposed method, which does not require any global dictionary tuning. As for VOC2006, the proposed method gives the best Mean Average Precision.

Dictionary sizes

EXPERIMENTS ON BATCH LEARNING

In this section, we present results for batch learning, where the goal is to build classifiers for a set of categories thanks to a large training set. In order to compute theses results, we followed the protocol named "comp1" in PASCAL Challenge for VOC 2006 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF]. Results are computed using the Matlab code provided with the database, which measures performance using the Area Under the ROC Curve (AUC). Results are displayed in Table 4 and detailed in the next sections.

Unsupervised visual dictionary

We have first carried out experiments using a global visual dictionary of colours and textures. This dictionary is created using K-means on the training set. We have tested several dictionary sizes, and it appears that a dictionary of 256 colours and 256 textures provides the best results, displayed in column (a) of Table 4. We used a SVM classifier with C = 1 and a Gaussian kernel with a χ 1 distance and σ = 0.5. One classifier is trained for each category. This method gets an average AUC of 85% and a MAP of 56%.

We have also carried out experiments using the state of the art approach: Vectors of Locally Aggregated Descriptors (VLAD) [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF], which is derived from the method based on bag of features and Fisher Kernels proposed in [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]. VLAD approach aggregates keypoint descriptors into a single vector in a more efficient way than bag of features. We have integrated this aggregation scheme using keypoints detected with Harris-Laplace and described with rgSIFT [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]. We have tested several dictionary sizes (from 8 to 64), and it appears that a dictionary of 32 visual words provides the best results, displayed in the second column of Table 4. The training procedure is the same, except that we used a Gaussian kernel with L 2 distance better adapted to VLAD descriptor. This method gets an average AUC of 89% and a MAP of 66% (column (b) of Table 4).

From this first experiments, it seems that the color and texture features are not as relevant as VLAD descriptor regarding classification of VOC 2006 data. In particular, the classifier using the global visual dictionary based on VLAD significantly outperforms colour and texture visual dictionary description on dog, cat or cow categories.

Supervised visual dictionary

In order to clearly illustrates the power of our supervised dynamic dictionary approach, we used it for batch learning and compared classification results with the previous ones on global dictionaries. However, using our method to build a visual dictionary while remaining in a classic batch learning context is not really relevant. Indeed, the dictionary is traditionally built on all the features in the images labelled as positive, which would make our incremental (dynamic) learning process useless. Furthermore, the evaluation of the kernel target alignment requires O(n 2 ) operations, with n the number of labels. In the context of batch learning, where training sets usually contain thousands of labels, these evaluations become intractable.

In order to circumvent these issues, we use our incremental method simulating retrieval sessions on the training sets, thus we build the visual dictionary by creating new features in an interactive retrieval framework. The idea is the following: if we store the classifier created at the end of a retrieval session, we get a good function to evaluate the relevance of any image in the neighborhood of the initial query image. Then, if we repeat such a process for each image of a category, we can represent any image with a "semantic descriptor" made of all the outputs from the classifiers of simulated retrieval sessions. This semantic descriptor based on supervised features relies on a category or a concept. A detailed presentation of this process is given in Algorithm 2. At last, we train a SVM classifier on the semantic descriptor corresponding to the category to retrieve.

Results with this approach are displayed on the column (c) of Table 4. This method achieves an average AUC of 89% and a MAP of 66%. If we compare these results to the one of the global dictionary of colours and textures, we can see the improvement of the learning process we propose, since both methods use the same low-level features. Our new process is at least as good as a global dictionary based on VLAD descriptor and even outperforms this state of the art method on the critical dog, cat and cow categories.

Combined supervised and unsupervised visual dictionaries

Finally, in order to compare somewhat fairly our approach to the current best method on PASCAL Challenge [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF], we have carried out experiments using the concatenation of all our supervised features and the global dictionary based on VLAD descriptors. This approach is an approximation of the original method from Perronnin et al. [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF] who creates a large vector for each image: one part being related to a global ("universal" in [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]) visual dictionary based on an unsupervised GMM trained on all data, and the other part is related to a supervised (category) visual dictionary using Gaussian Mixture Models trained on each category. Inspired by these works, [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] Jegou et al. proposed a simpler approach in which K-Means algorithm applied to VLAD descriptors approximates the universal visual dictionary and gets performance comparable to Perronnin et al. ones. We then concatenate the global VLAD vectors to our supervised "semantic" descriptors. In order to compare Perronnin et al. approach with our method, we have reported the results of [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF] in the column (e) of Table 4.

We have tuned the SVM and Gaussian kernel parameters following a twofolds cross validation between train and validation sets. Results are shown in the column (d) of Table 4. This method gets an average AUC of 93% and a MAP of 74%.

Performance is about the same, and thus illustrates the ability of our method to get very good results with less sophisticated image representations. In this paper, we introduced a framework to learn a kernel function during an interactive retrieval. This framework does not need any assumptions on the features, since the main requirement is an evaluation function which does not have to satisfy any special mathematical property. Furthermore, this framework allows the combination of features of different types, through evaluation functions adapted to each kind of feature (cf. Eq. ( 13)).

One application of this framework is the ability to build an optimal dictionary during the retrieval, instead of the tiresome step of cross validation, usually performed to build a global dictionary (hopefully the best one). Moreover, we showed on VOC 2006 database, that this automatically built dictionary has better performances than the best global dictionary, while still being compatible with an on-line use.

Another interest of our framework is that it dynamically builds the kernel function as new words are added to the dictionary. We also introduced an efficient active learning technique for this framework, based on the kernel target alignment.

This framework can be used with more complex features, for instance with keypoints or bags of features or even graphs, as long as an evaluation function can be defined. We are also working on extensions of this framework for long-term or collaborative learning, where the information given by past users is used to optimize the whole retrieval system.

  Proposed learning scheme with a dynamic dictionary

Figure 1 :

 1 Figure 1: Learning schemes for interactive image retrieval.

  as positive, otherwise as negative • For f from 1 to F do -Train a new classifier using current labels -Sort images of T using the classifier -Compute Precision/Recall curve pr(f, c) on T -I ⋆ f = s images selected in A using active learning -Label images of I ⋆ f ∩ C as positive, otherwise as negative Output: Average Precision/Recall curves P R(f ) = average c pr(f, c)

Figure 2 :

 2 Figure 2: Images from VOC 2006 database.

Figure 5 :

 5 Figure 5: Average computational time of each feedback step with dynamic histograms.

Figure 6 :

 6 Figure 6: Images from the Web.

Algorithm 2

 2 Supervised feature creation for one category using an interactive retrieval technique. Given: category C, training set A, number of feedbacks F , number of labels per feedback s For each image c of C ∩ A do • Create a new retrieval session with no labels • Initialization: -Label c as positive -I ⋆ 0 = s closest images to c in A -Label images of I ⋆ 0 ∩ C as positive, otherwise as negative • For f from 1 to F do -Train a new classifier f c using current labels -I ⋆ f = s images selected in A using active learning -Label images of I ⋆ f ∩ C as positive, otherwise as negative Output: Supervised feature vectors for images (I i ) i : S C i = f c (I i ) c∈C 7. CONCLUSION

  , and x i = (e pl (P i )) l . Evaluation protocol for one category Given: category C, training set A, test set T , number of feedbacks F , number of labels per feedback s

	Algorithm 1 For each image c of C ∩ A do
	• Create a new retrieval session with no labels
	• Initialization:

Table 1 :

 1 Average Precision(%) on the test set of VOC2006 database. Initialization with 1 image, 10 feedbacks, 5 labels per feedback. Except for the last column, results are shown for global dictionaries. The two numbers in column heads (for instance '160/64') are the sizes of the color and texture dictionaries. The last column shows results using the method proposed in this paper, where dictionaries are built during the retrieval. Figure 4: Average Precision on the test set of VOC 2006 database. Each square is the result for a combination of two dictionaries. A lighter square means a better performance than a darker one.

	Category 64/64 256/256 64/160 Dynamic
	bicycle	43	45	44	48
	bus	48	57	56	64
	car	65	69	70	79
	cat	28	28	30	31
	cow	47	35	40	41
	dog	22	23	23	25
	horse	22	24	23	25
	motorbike	46	55	50	61
	person	33	35	34	37
	sheep	48	38	48	36
	all	40	41	42	45

Table 2 :

 2 Average Precision(%) using the proposed method on the test set of VOC2006 database, according to the maximum number of words allowed in dynamic dictionaries. For experiments corresponding to the last column, the average number of words in each dictionary is between 150 and 200. Initialization with 1 image, 10 feedbacks, 5 labels per feedback.

		0.5
		0.45
	Computation time(s)	0.25 0.3 0.35 0.4 0.2					bicycle bus car cat cow dog horse motorbike person sheep
		0.15
		0 0.1	2	4	6	8	10
				Feedback step

Table 3 :

 3 Average Precision(%) on the database with images from the Web. Initialization with 1 image, 10 feedbacks, 5 labels per feedback. Except for the last column, results are shown for global dictionaries. The two numbers in column heads (for instance '128/512') are the sizes of the color and textures dictionaries. The last column shows results using the method proposed in this paper, where dictionaries are built during the retrieval.

	Category 512/64 256/256 128/512 Dynamic
	airplane	14	18	20	19
	beaver	6	10	9	7
	bikes	20	20	20	23
	boat	18	23	25	30
	camel	13	15	14	19
	car	26	34	38	38
	dolphin	17	20	23	20
	elephant	12	15	16	17
	giraffe	18	21	20	21
	guitar	26	26	23	27
	horse	14	15	15	17
	kangaroo	8	8	9	7
	motorbikes	13	16	18	19
	penguin	8	10	11	10
	shark	20	19	18	19
	tiger	11	17	19	19
	wristwatch	18	21	23	32
	zebra	25	44	50	56
	all	16	20	21	22

Table 4 :

 4 Area under ROC Curve(%) on the test set of VOC2006 database. lab = L ⋆ a ⋆ b ⋆ colors, qw = quaternionic wavelet textures, VLAD = Vector of Locally Aggregated Descriptors with Harris-Laplace/rgSIFT.


Marie-Pierre Béal

Dominique Perrin

Codes, unambiguous automata and sofic systems

HAL is

Introduction

This is the third of our papers on codes in sofic shifts. In the first one [START_REF] Béal | Codes and sofic constraints[END_REF], we have developed the point of view of measures and polynomials in the spirit of the Kraft-McMillan inequality. In the second one [START_REF] Béal | Complete codes in sofic systemsTo appear[END_REF], we have discussed the notions of complete and maximal codes in sofic shifts and their relationship. This generalization of the theory of (variable length) codes extends previous works of Reutenauer [START_REF] Ch | 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]. It is also related with recent work by Dalai and Leonardi [START_REF] Dalai | Non prefix-free codes for constrained sequences[END_REF], who study a close problem. They use Markov chains on the source symbols instead of constraints on the channel as we do. Codes with constraints on the source are also studied by Güney Gönenç in [START_REF] Gönenç | Unique decipherability of codes with constraints with application to syllabification of Turkish words[END_REF].

In this paper, we show how the use of unambiguous automata can be adapted to the framework of codes in sofic systems. This gives us a particular a method for checking whether a regular set is a code in a sofic shift. Another method generalizing the Sardinas-Patterson algorithm is also described.

We use these notions to discuss an interesting example of a complete code in a sofic system, in particular in connection with the factorization conjecture of Schützenberger. We show that its generalization to code in sofic shifts is not true.

We would like to thank Christophe Reutenauer and the anonymous referees for useful comments on an earlier version.

Codes in sofic systems

We begin with some definitions from symbolic dynamics. For a general reference, we refer to [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]. A sofic shift S is the set of bi-infinite sequences of symbols labelling paths in a finite automaton A = (Q, E), where Q is the set of states and E the set of edges. We say that A recognizes S. The set of factors of S, denoted by Fact(S), is the set of blocks appearing in the elements of S. An edge shift is the set of bi-infinite paths in a finite graph. A shift of finite type is the set of bi-finite sequences of symbols avoiding a finite set of words. An edge shift is a particular case of a shift of finite type, which is a particular case of a sofic shift. The full shift on a finite alphabet A is the set of all bi-infinite sequences of symbols in A.

A sofic shift is irreducible if it is recognized by an automaton with a strongly connected graph. There is a unique minimal deterministic automaton recognizing a given irreducible sofic shift. It is called the Fischer cover of the shift.

Example 1 Let S be the irreducible sofic shift whose Fischer cover is represented in Figure 1. This shift is called the even system. It is a sofic shift which is not of finite type. Let S be a sofic shift over the alphabet A. We denote by Z[S] the algebra of linear combinations with coefficients in Z of elements of Fact(S) using the product

u • v =    uv if uv ∈ Fact(S) 0 otherwise.
For U ∈ Z[S] and w ∈ Fact(S), we denote by (U, w) the coefficient of w in U. We denote by N[S] the set of linear combinations with coefficients in N of elements of Fact(S). We also use the corresponding large algebra which consists of the infinite linear combinations of elements of Fact(S). We often identify a subset of Fact(S) with the sum of all its elements. We have in particular the equation in the large algebra.

(

-A) Fact(S) = Fact(S)(1 -A) = 1. 1
We may as well write Fact(S) = A * , provided the star operation is understood to refer to the product defined above.

A set X of elements of Fact(S) is called an S-code if any element of Fact(S) has at most one decomposition in code words. We also say that X is a code in S. Thus a code in the usual sense is a code in the full shift. A set of words X is S-complete (or complete in S) if any element of Fact(S) occurs within some concatenation of elements of X.

It is known that a maximal S-code is S-complete (see [START_REF] Béal | Complete codes in sofic systemsTo appear[END_REF]). The converse is not true since for example X = {ab} is complete in the shift of finite type avoiding aa and bb. However, it is not maximal since it is included in {ab, ba}.

If X is an S-code, we have in the large algebra of Fact(S)

(1 -X)X * = X * (1 -X) = 1,
where the star operation is again understood to refer to the product defined above.

A prefix code in a sofic shift S is a set X of elements of Fact(S), such that no proper prefix of a word of X belongs to X. A set of words X is right complete in S if any element of Fact(S) is a prefix of a word in X * . A prefix code which is maximal is right-complete and conversely (the proof is the same as in the case of the full shift). It is not true however that a prefix code in a sofic shift which is complete is also right-complete as shown by the example of X = {ab}.

Let X be a maximal prefix code in a sofic shift S, and let P be the set of proper prefixes of words of X. We have in the large algebra of Fact(S) the equations

X -1 = P (A -1), Fact(S) = X * P.
For example, if S is the subshift of finite type avoiding aa and bb, and if X = {ab, ba}, we have in the algebra of Fact(S)

X -1 = (A + 1)(A -1).
Interestingly, for X = {ab}, we do not have such an identity because it is not maximal. But we have the 3-factors product

X -1 = (a + 1)(a + b -1)(b + 1).

Unambiguous automata

There are at least two methods which can be used to check whether a set X is a code, the classical Sardinas-Patterson algorithm and the test of unambiguity for automata. We extend here these methods to codes in sofic systems. The extension of the Sardinas-Patterson algorithm to codes in edge shifts has already been described by C. Reutenauer in [START_REF] Ch | Ensembles libres de chemins dans un graphe[END_REF].

We begin with the extension of the Sardinas-Patterson algorithm. Let S be a sofic system and let X be a subset of Fact(S). Let A = (Q, E, i, T ) be the minimal deterministic automaton of Fact(S). We consider the following notion on subsets of

A * × Q. For U, V ⊆ A * × Q, let U -1 V = {(w, q) | (uw, q) ∈ V and p w -→ q for some (u, p) ∈ U}.
We denote

Y = {(x, p) | x ∈ X, p ∈ Q and i x -→ p}.
We then define a sequence (U n ) n≥0 of subsets of A * × Q by the usual formulas.

U 0 = Y -1 Y -{(ε, p), p ∈ Q}, U n+1 = Y -1 U n ∪ U -1 n Y.
It is easy to verify that there is a finite number of possible sets (U n ) n≥0 when X is finite (it is also true when X is regular). The proof of the following result is similar to the classical one.

Proposition 1 The set X is a code if and only if none of the sets U n contains a pair (ε, p) with p ∈ T .

Example 2 We consider the even shift S of Figure 1. Its set of finite factors is recognized by the automaton of Figure 2.

Let X = {a, ab, ba}. We have Thus X is an S-code although it is not a code in the full shift. We will have more to say about this example later (Section 4).

Y = {(a, 1), (ab, 2), (ba, 1)}, U 0 = {(b, 2)}, U 1 = ∅.
We now come to the method using automata. It is well known that for a set X of words, one can construct a non-deterministic automaton such that X * is the stabilizer of one state and that X is a code if and only if this automaton is unambiguous (see [START_REF] Berstel | Theory of Codes[END_REF]). Such an automaton also allows one to check easily whether the code is complete. We extend below this method to codes in sofic systems.

Recall that a nondeterministic automaton is unambiguous if whenever there are two paths of the form

p u -→ r v -→ q p u -→ s v -→ q,
we have r = s. In other terms there is a unique path with a given origin, end, and label.

Let S be an irreducible sofic system on the alphabet A and let X ⊂ Fact(S) be a set of words. We suppose in a first step that X is a finite set. As we shall see later, the construction below also works for a regular set X.

Let A = (Q, E) be the minimal deterministic automaton recognizing S (see [START_REF] Béal | Symbolic dynamics and finite automata[END_REF] for an exposition of the links between automata and symbolic systems).

We build an automaton B as follows. The set of states is formed by the set Q plus |x| -1 new states for each path in A of the form p x → q for x ∈ X. It is easy to verify that the automaton B recognizes X * ∩ Fact(S) with Q as set of initial and terminal states.

When X is regular, we proceed as follows. Let C = (P, F, i, t) be an unambiguous normalized automaton recognizing X. A classical construction (see [9, p. 185]) allows one to build an automaton C * = (P ∪ ω, ω, ω), where ω is a new state obtained by merging the states i and t, such that the number of paths from ω to ω labeled by w is the number of factorizations of w in words of X. The automaton B is now chosen as A × C * . The previous construction corresponds to the choice of the flower automaton of the set X for C * .

The following statement shows in particular that one can use the automaton B to verify whether X is an S-code.

Proposition 2

The set X is an S-code if and only if the automaton B is unambiguous.

PROOF. For any two states p, q in Q, let L pq be the set of words labels of paths from p to q in A. Each state of B is accessible and co-accessible from a state in Q × ω. Hence B is unambiguous if and only if, for any pair p, q of states of Q and any word w, there is at most one path in B labeled by w from (p, ω) to (q, ω). By construction, the number of paths from (p, ω) to (q, ω) labeled by w is the number of factorizations of w in words of X. Thus if X is an S-code, B is unambiguous. Conversely, if X is not an S-code, there is a word w ∈ L pq for some states p, q ∈ Q which has at least two factorizations in words of X, which implies that B is ambiguous. 2 Example 3 For the set X = {a, ab, ba} of Example 2 in the even shift, the automaton B is represented in Figure 3. It is an unambiguous automaton. A lookahead of one symbol suffices to resolve the nondeterminism in state 1. This gives a second proof that X is an S-code. Moreover, the automaton B can be used to verify whether X is S-complete. Indeed Proposition 3 The set X is S-complete if and only if B recognizes S.

In practice, if S is irreducible, since B recognizes a subshift T of S, it is enough to verify that the entropy of T is equal to the entropy of S. This can be done in polynomial time (see [START_REF] Béal | Computing forbidden words of regular languages[END_REF]).

A complete code in the even system

In this section, we develop in some detail an example of a complete code in a sofic system. We consider again the set of words X = {a, ab, ba}. It is the simplest example of a set which is not a code. In fact, one has the two factorizations (ab)(a) = (a)(ba). However, one has the following statement Proposition 4 The set X is a code in any sofic system such that the block aba is forbidden.

PROOF. The simplest way to see this is as follows. An ambiguous factorization should begin with (a)(b • • • = (ab) • • • . Since aba is forbidden, the prefix ab should be followed by a b as (a)(bb

• • • = (ab)(b • • • which is clearly impos- sible. 2
For example, the set X is a code in the system S aba which is represented on Figure 4, which is the subshift of finite type on the alphabet A = {a, b} defined by the unique forbidden block aba. We will verify the following statement.

Proposition 5

The code X cannot be finitely completed in the system S aba .

PROOF. Let us assume the contrary and let Y be a finite complete code in S aba containing X.

Let n ≥ 1 be such that b n ∈ Y . Then (a)(b n )(ba) = (ab)(b n )a, a contradiction. 2
This contrasts with the situation for codes (in the full shift) for which the simplest example of a code without any finite completion (i.e. the set {a 5 , b, ab, ba 2 }) relies on counting modulo some integer (see [START_REF] Restivo | On codes having no finite completions[END_REF] or [9, p. 64]).

The set X is also a code in the even system represented on Figure 1. Let us now consider the following set containing X. Y = {a, ab, ba, bab, bbbb}.

We are going to verify that, in contrast with the previous proposition, the following holds.

Proposition 6

The set Y is a complete code in the even system.

PROOF. The fact that Y is a code follows from Proposition 1. To see that it is complete, we compute the automaton recognizing Y * as indicated by the method of Section 3. Up to the merge of some states, we obtain the automaton shown on Figure 5. It recognizes Y * with 1 and 3 as initial and terminal states. A part of the subset construction applied to this automaton and represented on Figure 6 constitutes an automaton with five states {1, 2}, {3, 7}, {4, 8}, {1, 5} and {6, 9} recognizing the even system. This can be seen by minimizing the deterministic automaton with these five states, which gives the Fischer cover of the even system. Thus the code is complete in this system. 2 Thus the polynomial of the code is

p(Y ) = 1 -a -2b 4 -a 2 b 2 -ab 2 + (a + b 4 )(ab 2 + b 4 ) = 1 -a -ab 2 -2b 4 + ab 4 + ab 6 + b 8 .
In accordance with the main result of [START_REF] Béal | Complete codes in sofic systemsTo appear[END_REF], the polynomial p(Y ) is divisible by p(A) = 1ab 2 . Indeed, we have

p(Y ) = (1 + b 2 )(1 -a -b 2 )(1 -b 4 ).
It is interesting to remark that this factorization can be lifted to a noncommutative one. Indeed, one has in non-commuting variables

   1 -a -b 4 -ab -ba 1 -bab -b 4    =    1 0 b 1 + b 2       1 -a -b -b 1       1 b b 3 1   
Thus, we have obtained the existence of matrices P, Q with elements in the subsets of A * such that

I -M(Y ) = P (I -M(A))Q. (1)
We will have more to say on this equation in the next section.

A complete code in an edge shift

We finally consider what happens if one replaces the even system by the subshift of finite type S represented on Figure 8 and consisting in giving distinct names to the edges of the automaton of the graph of Figure 1. This is actually the edge shift of the graph of Figure 1. We replace Y by the set Z = {a, ab, ca, cab, bcbc, cbcb} obtained by renaming the paths labeled by the words of Y in the graph of the automaton recognizing the even system. The set Z is again a complete code in S. The matrix M(Z) is

M(Z) =    a + bcbc ab ca cab + cbcb   
and we have the factorization

   1 -a -bcbc -ab -ca 1 -cab -cbcb    =    1 0 c 1 + cb       1 -a -b -c 1       1 b cbc 1   
This factorization has the same form I -M(Z) = P (I -M(A))Q as the factorization (1) but this time, the matrices P, Q are the matrices of the action of sets U, V with U = {1, c, cb}, V = {1, b, cbc}. We can even write simply

1 -Z = U(1 -A)V, (2)
provided the expressions on both sides are computed in the algebra Z[S].

A finite subset Z of Fact(S) such that there exists two polynomials U, V ∈ Z[S] (resp. two sets U, V ⊆ Fact(S)) satisfying Equality ( 2) is called Z-factorizing (resp. N-factorizing).

An N-factorizing set is an S-complete code. Indeed, Equation ( 2) is equivalent to Fact(S) = V (1 -Z) -1 U in the large algebra of Fact(S). The last equality implies that (1 -Z) -1 has coefficients equal to 0 or 1, and thus that it is an S-code. It also implies that it is S-complete. It is conjectured that any finite complete code in the full shift is N-factorizing. This is called the factorization conjecture (see [START_REF] Berstel | Theory of Codes[END_REF]).

C. Reutenauer has proved that any finite complete code in the full shift is Z-factorizing (see [START_REF] Berstel | Ch. Reutenauer, Rational Series and their Languages[END_REF]). He has conjectured in [START_REF] Ch | Ensembles libres de chemins dans un graphe[END_REF] that any finite code which is complete and minimal for this property in an edge shift is Z-factorizing.

The following statement shows that the extension to sofic shifts of Reutenauer's conjecture is not true. Indeed, the set Y defined below is a complete code in the even system by Proposition 6. It is also minimal for this property as one may verify.

Proposition 7

The code Y = {a, ab, ba, bab, bbbb} is not Z-factorizing in the even shift.

PROOF. Let S be the even shift. Suppose that U, V are two polynomials in Z[S] such that 1 -Y = U(1 -A)V . Since any word in Y has at most one occurrence of a, the monomials of U and V belong to b * . The equation

Fig. 1 .

 1 The even system.

Fig. 2 .

 2 Fig. 2. A deterministic automaton recognizing Fact(S).

Fig. 3 .

 3 Fig. 3. The unambiguous automaton B.

Fig. 4 .

 4 Fig. 4. The system S aba .

Fig. 5 .

 5 Fig. 5. An automaton recognizing Y * .

Fig. 6 .

 6 Fig. 6. The state diagram.We now consider the polynomial of the code Y . This is by definition the determinant of the matrix I -M(Y ) (with entries in Z[A]), where M(Y ) is the matrix associated with the action of the words of the code on the minimal automaton of the shift. This action is represented on Figure7.The matrix M(Y ) is

Fig. 7 .

 7 Fig. 7. The action of Y on the even system.

Fig. 8 .

 8 Fig. 8. A subshift of finite type.

which is a contradiction. 2


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

Dominique Perrin
email: perrin@univ-mlv.fr

Codes and sofic constraints

We study the notion of a code in a sofic subshift. We first give a generalization of the Kraft-McMillan inequality to this case. We then prove that the polynomial of the alphabet in an irreducible sofic shift divides the polynomial of any finite code which is complete for this sofic shift. This settles a conjecture from Reutenauer.

Introduction

There is a rich and fruitful interplay between two theories which arose at first independently. One is the theory of automata and formal languages, born in the context of theoretical computer science. The other one is symbolic dynamics which arose from the theory of dynamical systems in topology and probability theory. The theory of variable-length codes is one of the contact points between these domains, with a counterpart in symbolic dynamics in renewal systems and finite-to-one maps. Antonio Restivo has initiated in [START_REF] Restivo | Codes and local constraints[END_REF] a new direction by studying systematically the notion of a code in a subshift of finite type. In particular, he has studied the relationship between maximal and complete codes, with results that essentially extend those known in the case of the free monoid, or equivalently the full shift in symbolic dynamics.

In this paper, we continue this exploration. First of all, we adopt a definition which is not exactly the same one. To be more specific, we consider a sofic shift S and a subset X of the set F S of factors of S. We consider such a set X which is a code. Observe that we do not require, as in [START_REF] Restivo | Codes and local constraints[END_REF] and [START_REF]Codes with constraints[END_REF] that X * ⊂ F S . This modifies the subsequent notions of an S-complete or S-maximal code. Actually, our notion has also connections with the definition of a code in a graph introduced by Christophe Reutenauer in [START_REF] Ch | Ensembles libres de chemins dans un graphe[END_REF], as we shall see below. The case of bifix codes was studied by Clelia De Felice in [START_REF] Felice | Finite biprefix sets of paths in a graph[END_REF]. Codes in subshifts have also a connection with the study of permutation groups in syntactic semigroups (see [START_REF] Perrin | Syntactic groups[END_REF]).

We first show that one may generalize to this situation the classical Kraft-McMillan inequality. In fact, we associate to each set X of words a series p X (z) which, in the case where S is the full shift, reduces to the generating series of the words of X by length, i.e. p X (z) = n≥1 u n z n where u n is the number of words of length n in X. Let h(S) be the entropy of S and let ρ S be such that h(S) =log(ρ S ). The precise definition of the entropy is given in the next section. It uses a logarithm and the same basis has to be used in both definitions of ρ S and h(S). In particular, ρ S = 1/k when S is the full shift on k symbols. We prove that if X is a code, then p X (ρ S ) ≤ 1. Actually, we obtain this result as a corollary of a more general one, corresponding to an assignment of real values to the letters generalizing the notion of a Bernoulli distribution (Theorem 1). We say that X is S-complete if X ⊂ F S ⊂ F (X * ), where F (X * ) denotes the set of factors of the words in X * . We prove that when X is regular, then p X (ρ S ) = 1 if and only if X is S-complete. This is again obtained as a corollary of a more general result (Theorem 2).

We prove in a second part of the paper a generalization of a result of [8] concerning a multivariate polynomial p(X) associated with a code X, called the determinant of the code. It says that, for a finite S-complete code, where S is an irreducible sofic shift, this polynomial is divisible by the polynomial p(A). The proof uses the results of the previous section, in contrast with the algebraic arguments of [START_REF] Ch | Ensembles libres de chemins dans un graphe[END_REF] using the notion of syntactic category, a generalization of the syntactic semigroup.

Codes and sofic shifts

Let A be a finite alphabet. We denote by A * the set of 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 by 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. A sofic shift is the set of labels of all bi-infinite paths on a finite automaton. A sofic shift is irreducible if there is such a finite automaton with a strongly connected graph. If A is deterministic, for any state p ∈ Q and any word u, there is at most one path labelled u and going out of p. We denote by p • u the target of this path when it exists. 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 right Fischer cover of the shift. A subshift of finite type is defined as the biinfinite words on a finite alphabet avoiding a finite set of finite words. It is a sofic shift. An edge shift is the set of the labels of all bi-infinite paths on a finite automaton where all edges have distinct labels. The full shift on the finite alphabet A is the set of all bi-infinites sequences on A, i.e. A Z .

Let S be a subshift on the alphabet A. We denote by F S the set of finite factors, or blocks, of words in S. We denote by h(S) the entropy of a S. It is equal to entropy h(L) of the language L = F S , where

h(L) = lim sup n→∞ 1 n log Card(L ∩ A n ).
We denote by ρ S the unique positive real number such that h(S) = log(1/ρ S ).

The positive real number ρ S is the convergence radius of the generating series of L by length.

Example 1 If S be the full shift on A, then ρ S = 1/ Card(A).

Example 2 Let S be the irreducible subshift of finite type on A = {a, b} defined by the finite set of forbidden sequences I = {bb}. It is the so-called golden mean system, and ρ S is the inverse of the golden mean, solution of ρ 2 S = 1ρ S . The right Fischer cover of S is represented on Figure 1. A set of finite words X on an alphabet A is a code if and only if whenever x 1 x 2 . . . x n = y 1 y 2 . . . y m , where x i , y j ∈ X and n, m are positive integers, one has n = m and x i = y i for 1 ≤ i ≤ n. If X is set of finite words on a finite alphabet, X * denotes all finite concatenations of words of X.

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 ⊂ F S , and any word in F S is a factor of a word in X * . Observe that we do not require that X * ⊂ F S .

A code X is S-maximal if X ⊂ F S and it is maximal for this property.

Let S be an irreducible sofic shift over the alphabet A. Let (Q, E) be its right Fischer cover. Let µ be the morphism from A * into the monoid of Q × Q matrices over the monoid A * ∪ {0} defined as follows. For each word u, the matrix µ(u) is defined by

µ(u) pq = u if p • u = q 0 otherwise.
The elements of the matrix µ(u) can be considered as subsets of A * , interpreting 0 as the empty set. The morphism µ can be extended to the semiring P(A * ) of subsets of A * by linearity. Thus, it becomes a morphism from P(A * ) to the semiring of Q × Q matrices on P(A * ).

For any subset X of A * , we have

µ(X n ) = µ(X) n , and
µ(X * ) = n≥0 µ(X n ).
We denote by π an assignment of positive real values to the elements of A. We extend it to a semigroup morphism from A * ∪ {0} to R. We denote by u → f u (z) the morphism from A * into the monoid of Q × Q matrices with coefficients in the polynomial ring R[z], defined for each word w by

f u (z) pq = π(u)z |u| if p • u = q 0 otherwise.
If U is a set of words, we denote by f U (z) the matrix whose coefficients are real power series defined by

f U (z) = u∈U f u (z).
Actually, f U (z) can also be considered as a series whose coefficients are real matrices. In this sense, we will talk about the radius of convergence of f U (z) and denote it by ρ(f U (z)). It is the minimum of the radii of convergence of its elements when viewed as a matrix. Note that, for a set of words U , the elements of the matrix f U (z) are obtained from the elements of µ(U ) as the generating series of the values by π. More precisely

f U (z) pq = π(u)z |u| ,
where the sum runs over all

u ∈ µ(U ) pq . If X is a code, then f X n (z) = (f X (z)) n ,
and

f X * (z) = (I -f X (z)) -1 .
We consider the polynomial d(z) = det(I -f A (z)). We say that an assignment π is admissible if the following condition is satisfied: the value z = 1 is a root of d(z) and |θ| ≥ 1 for any other root θ.

There is always at least one admissible assignment for each nonempty alphabet. For instance, one can show that the assignment defined by π(a) = ρ S for any a ∈ A is admissible (see for example [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]).

An admissible assignment can be seen as a generalization of a Bernoulli distribution on the alphabet. Actually, when S is the full shift on A, both definitions coincide. Indeed, in this case, f A (1) = a∈A π(a) and thus π is admissible if and only if a∈A π(a) = 1.

Note that, when π is admissible, the radius of convergence of f A * (z) is 1. Indeed, for every complex number z such that |z| < 1, det(If A (z)) = 0 and thus f A * (z) converges.

The following example describes the admissible assignments in the case of the golden mean system.

Example 3 We consider again the golden mean system of Example 2. The morphism µ is defined by:

µ(a) = a 0 a 0 , µ(b) = 0 b 0 0 . Let π(a) = p, π(b) = q.
We have

f a (z) = pz 0 pz 0 , f b (z) = 0 qz 0 0 , f A (z) = pz qz pz 0 . Hence d(z) = 1 -pz -pqz 2 . Thus π is admissible if and only if p(1 + q) = 1. In particular, π(a) = π(b) = ρ S is admissible.
Our first result is the following statement.

Theorem 1 Let S be an irreducible sofic shift and let π be an admissible assignment. If X ⊂ A + is a code, then the series f X (z) converges for z = 1 and det(If X (1)) ≥ 0.

Proof Let A = (Q, E) be the right Fischer cover of S. For any two states p, q ∈

Q, µ(X * ) pq ⊆ µ(A * ) pq . Thus ρ(f X * (z)) ≥ ρ(f A * (z)). Since π is admissible, ρ(f A * (z)) = 1. It follows that ρ(f X * (z)) ≥ 1. Since X is a code, f X * (z) = (I -f X (z)) -1 . Thus det(I -f X (z)) = 0 for 0 ≤ z < 1. Since det(I -f X (0)) = 1,
we obtain det(If X (z)) ≥ 0 for 0 ≤ z < 1 by continuity. Again by continuity we conclude that det(If X (1)) ≥ 0.

Example 4 Let S be the golden mean system and let X = {aa, ab}. Let π(a) = p, π(b) = q be an admissible assignment, i.e. such that p(1 + q) = 1. We have

f X (z) = p 2 z pqz 2 p 2 z pqz 2 .
Hence det(If X (1)) = 1p 2pq which is at most equal to 1.

We will now prove a complement to Theorem 1 describing the equality case. The proof uses the following lemma stating a classical property on regular languages. If u is word and L a set of finite words, u -1 L denotes the set {w ∈ A * | uw ∈ L}.

Lemma 1 If L is a regular language of finite words, then there is a finite subset

P of A * such that the set of factors F (L) of L satisfies F (L) ⊆ v,w∈P v -1 Lw -1 .
Proof Let A = (Q, I, T, E) be a finite automaton recognizing the language L with I the set of initial states, T the set of terminal states, and E the set of edges. We may assume that, for each state q ∈ Q, there exist (i, t) ∈ I × T and two words v q , w q such that i vq -→ q wq --→ t. For each word u ∈ F (L), there exist p, q ∈ Q such that p u -→ q. Thus v p uw q ∈ L. This shows that F (L) ⊆ p,q∈Q v -1 p Lw -1 q .

Theorem 2 Let S be an irreducible sofic shift and let π be an admissible assignment. If X ⊂ F S is a regular code, then X is S-complete if and only if det(If X (1)) = 0.

Proof Let A = (Q, E) be the right Fischer cover of S. Let p be a state of A. If X is S-complete, any word u in F S with p • u = p is a factor of a word in X * . If u is factor of word in X, then there are states s, t ∈ Q such that u is factor of a word in µ(X) st , since X ⊂ F S . If u is not factor of a word in X, by considering the words u n , for n ≥ 1, we get that u is factor of some word in µ(X * ) st , for some states s, t ∈ Q. It follows that, in any case, there are two states s, t ∈ Q such that u is factor of a word in µ(X * ) st . Since X is regular, µ(X * ) st is also regular. It follows from Lemma 1 that, for each p ∈ Q, there is a finite set of words U such that

µ(A * ) pp ⊂ s,t∈Q v,w∈U v -1 µ(X * ) st w -1 .
For any

s, t ∈ Q, any v, w ∈ A * , ρ(f v -1 µ(X * )stw -1 (z)) ≥ ρ(f µ(X * )st (z)) ≥ ρ(f X * (z)). Thus ρ(f A * (z)) ≥ ρ(f X * (z)). Since π is admissible, ρ(f A * (z)) = 1. By Theo- rem 1, ρ(f X * (z)) ≥ 1. Hence ρ(f X * (z)) = 1.
Since X is a regular code, for any two states p, q ∈ Q, f X * (z) pq is a rational series with nonnegative real coefficients. By Lemma [2, Lemma 2.3 pp.82], either f X * (z) pq is a polynomial, or the minimal modulus of the poles of

f X * (z) pq is itself a pole. Since f X * (z) = (I -f X (z)) -1 , it follows that det(I -f X (z)) vanishes at 1.
Conversely, let us assume that X is not S-complete. There is a word u ∈ F S such that u is not factor of any word in X * . Thus X * ⊆ A * -A * uA * .

Because S is irreducible and π assigns a positive real value to each letter, the matrix f A (1) is an irreducible nonnegative real matrix. Thus, it follows from Proposition [4, Theorem 4.4.7] that, for p, q ∈ Q, ρ(f

A * -A * uA * (z) pq ) > ρ(f A * (z) pq ).
We get that, for any states p, q ∈ Q,

1 = ρ(f A * (z)) ≤ ρ(f A * (z) pq ) < ρ(f A * -A * uA * (z) pq ) ≤ ρ(f X * (z) pq ).
Hence ρ(f X * (z)) > 1. This implies that det(If X (1)) > 0.

We now derive from Theorem 1 and Theorem 2 two corollaries which constitute a generalization of the Kraft-McMillan inequality. Let π be the admissible assignment defined by π(a) = ρ S for any a ∈ A. For a subset X of A * , we denote for convenience

p X (z) = 1 -det(I -f X (z/ρ S )).
Thus p X (ρ S ) = 1det(If X (1)). When S is the full shift on k symbols ρ S = 1/k and p X (z) = n≥1 u n z n , where u n is the number of words of length n in X. Thus the inequality p X (ρ S ) ≤ 1 takes the form n≥1 u n k -n ≤ 1, which is the Kraft-McMillan inequality.

Corollary 3 Let S be an irreducible sofic shift. If X ⊂ A + is a code, then p X (ρ S ) ≤ 1.

Corollary 4 Let S be an irreducible sofic shift and let X ⊂ F S be a regular code. The code X is S-complete if and only if p X (ρ S ) = 1.

The following examples illustrate the different possible cases. The first two ones give examples of S-complete codes.

Example 5 Let S be the golden mean system. The set X = a + ab is both a code and an S-complete set. We have p X (z) = z + z 2 and thus p X (ρ S ) = 1.

Example 6 Let S be the golden mean system again. Let X = aa + ab + ba. The set X is an S-complete code since it is formed of all factors of length 2 of S. We have p X (z) = 3z 2z 4 , and p X (ρ S ) = 3ρ 2 Sρ 4 S = 1.

The last example shows a case of a code which is not S-complete.

Example 7 Let S be the even system represented on Figure 2. The set X = b(a 2 ) * b is a code. It is not S-complete. The value of ρ S is the same as for the golden mean system. We have

f X (z/ρ S ) = z 2 (z 2 ) * 0 0 0 , and p X (z) = 1 -(1 -z 2 (z 2 ) * ) = 1 -(1 -z 2 1-z 2 ) = z 2 1-z 2 . Hence p X (ρ S ) = 2 1+ √ 5 < 1.
We briefly investigate the relation between the extremal properties of being S-complete and S-maximal. It is shown in [START_REF]Codes with constraints[END_REF] (and it is also a consequence of a result of [START_REF] Ashley | Surjective extensions of sliding-block codes[END_REF]) that, when S is a subshift of finite type, any S-maximal code is S-complete (with the definitions of an S-code given in [START_REF]Codes with constraints[END_REF]). The result still holds for shifts of finite type with our definitions of S-maximal and S-complete codes.

Conversely, there is an example in [START_REF] Ch | Ensembles libres de chemins dans un graphe[END_REF] of an S-complete code which is not Smaximal. Indeed, consider the shift S described in Figure 3. The code X = {ab} is S-complete and not S-maximal since it is included in {ab, ba}.

Factorization

In this section, we consider the case where X is a finite code, and S is an irreducible sofic shift with A as right Fischer cover. We prove that the polynomial of the alphabet for S divides the polynomial of any finite code X which is complete for S. Both polynomials are defined below. This settles a conjecture from Reutenauer given in [8, pp. 150]. In [8, pp. 150], Reutenauer proves the same result when S is an edge shift satisfying a constraint called the condition (0): each state of its right Fischer cover has a loop. Let us denote by α the morphism obtained from µ by taking the commutative image of the elements. For any finite code X, the polynomial p(X) = det(Iα(X)) is in Z[A], the set of polynomials over Z in the commuting variables a in A. The polynomial det(If X (z)) and p X (z) are of course closely related to p(X). Indeed, for any point x = (π(a)z) a∈A , where π is an assignment, det(If X (z)) = p(X)(x), where p(X)(x) denotes the value of p(X) at the point x.

Theorem 5 Let S be an irreducible sofic shift. When X is a finite S-complete code, the polynomial p(X) is a multiple of the polynomial p(A).

Proof We first assume that S is an irreducible edge shift.

It is known that det(Iα(A)) is equal to

1 + k≥1 (-1) k c1...c k α(c 1 ) . . . α(c k ),
where the second sum is over all simple cycling paths c 1 , . . . , c k of S which do not share any state, two by two. If c is such a simple cycling path, α(c) denotes its label seen as a monomial of N[A]. Since S is an irreducible edge shift, the partial degree of p(A) in each letter is at most 1 and all its monomials have coefficients 1 or -1.

Moreover, it is proven in [8, Theorem 3] that p(A) is an irreducible polynomial of Z[A].
Let a be a letter appearing in a simple cycling path c with α(c) = au, and B = A -{a}. Thus u is a word of commutative letters in B. It follows from the above remarks that p(A) = -au(1q) + 1 + r, where q and r are polynomials in Z[B] with no constant term. The polynomials p(X) and p(A) can be seen as polynomials in a with coefficients in Z[B]. We now divide p(X) by

p(A) in Z[A, 1 u(1-q) ]. Thus p(X) = p(A) s + t,
where s and t are polynomials in Z[A, 1 u(1-q) ] which are respectively the quotient and the rest of this division. The degree of t in a is zero. It follows that there is a positive integer n such that

p(X)(u(1 -q)) n = p(A) s ′ + t ′ , with s ′ ∈ Z[A], t ′ ∈ Z[B].
Let π be an admissible assignment. We denote by π the point π = (π(a) = ρ S ) a∈A . Let w = (π(b) = ρ S ) b∈B . We get

p(A)(π) = det(I -α(A))(π) = det(I -f A (1)) = 0. Hence (au(1 -q))(π) = (1 + r)(π), or ρ S = (1 + r)(w) (u(1 -q))(w)
.

We denote by B(w, ε) the ball of dimension Card(B) and radius ε > 0 centered at w. A positive ball is a ball containing only points with positive coefficients. There is a positive ball B(w, ε) such that, for any point denoted x = (x 1 , . . . , x |B| ) in B(w, ε), (1+r)(x) (u(1-q))(x) > 0, and the assignment π x defined by

π x (b) = x b if b ∈ B, π x (a) = (1 + r)(x) (u(1 -q))(x)
, is admissible. Indeed, since S is irreducible, by the Perron-Frobenius theorem, z = 1 is a simple root of det(If A (z)) with the assignment π. Moreover, the roots of modulus 1 are e 2iπ/k for 0 ≤ k ≤ m -1, where m is a positive integer. By definition of π x , z = 1 is still a root of det(If A (z)) with the assignment π x . When x is close enough to w, it is the single positive real root of modulus less than or equal to 1. Thus, again by the Perron-Frobenius theorem, any root of det(If A (z)) with the assignment π x has a modulus greater than or equal to 1. Hence π x is admissible.

By Theorem 2, p(X)(π) = 0 and p(A)(π) = 0 for any π = (π(a)) a∈A where π is an admissible assignment. We get that t ′ vanishes at any point in B(w, ε).

Because B(w, ε) has dimension Card(B), we conclude that t ′ vanishes, and p(A) divides p(X)(u(1-q) n . Since p(A) is irreducible and has a monomial containing the letter a, p(A) divides p(X) in Z [A].

We now extend the result for irreducible edges shifts to irreducible sofic shifts.

Let S be an irreducible sofic shift and let A be its right Fischer cover. We denote by A ′ the automaton obtained from A as follows. For any a ∈ A, if there are m edges labelled by a in A, one labels these edges by a 1 , . . . , a m respectively in A ′ . We denote by A ′ the finite alphabet formed of the letters with indices. Since all edges of A ′ have distinct labels, A ′ is the right Fischer cover of an irreducible edge shift S ′ . We denote by ϕ the map assigning a to each a i , for any a ∈ A, and its extension as a morphism from A ′ * to A * . Note that, for each path p u -→ q in A, there is a unique path p

u ′ -→ q in A ′ with ϕ(u ′ ) = u, since A is deterministic.
Let X be a finite S-complete code. We define the finite set of words X ′ as the set of labels v of all paths in A ′ such that ϕ(v) ∈ X.

We claim that X ′ is a code. Indeed, whenever

u ′ 1 u ′ 2 . . . u ′ r = v ′ 1 v ′ 2 .
. . v ′ s , with r, s positive integers, and

u ′ i , v ′ j ∈ X ′ , we have ϕ(u ′ 1 )ϕ(u ′ 2 ) . . . ϕ(u ′ r ) = ϕ(v ′ 1 )ϕ(v ′ 2 ) . . . ϕ(v ′ s ).
Since X is a code, r = s and ϕ(u

′ i ) = ϕ(v ′ i ) for any 1 ≤ i ≤ r. It follows that |u ′ i | = |v ′ i | for any 1 ≤ i ≤ r and finally u ′ i = v ′ i .
We claim that X ′ is a finite S ′ -complete code. Since A is a minimal deterministic automaton recognizing the sofic shift S, it has a strongly connected graph and a synchronizing word (or reset sequence) u. A synchronizing word in a deterministic automaton is a word u such that the cardinality of the set

Q • u = {p • u | p ∈ Q} is one. Hence Q • u = {q 0 }.
Moreover u is the label of a path from p to q 0 in A, where p is some state in Q.

Let w ′ be a factor in F S ′ . There is path q w ′ -→ r in A ′ and a path q w -→ r in A with ϕ(w ′ ) = w. Let x, y and z be words of A * labels of paths from q 0 to p, from q 0 to q, and r to p, respectively. Hence we have in A the path

q 0 x -→ p u -→ q 0 y -→ q w -→ r y -→ p u -→ q 0 .
Since X is S-complete, xuywzu is a factor of a word in X * . Moreover, there are two states s, t ∈ Q such that xuywzu is factor of a word in µ(X * ) st (see the beginning of proof of Theorem 2). As a consequence, and since u is synchronizing, there are words g, h ∈ A * such that

s g -→ q 0 y -→ q w -→ r z -→ p u -→ q 0 h -→ t is a path in A labelled by a word in X * . Let s g ′′ -→ q 0 y ′′ --→ q w ′′ --→ r z ′′ -→ p u ′′ --→ q 0 h ′′ --→ t
be the unique path in A ′ such that ϕ(l ′′ ) = l for l = g, y, w, z, u, and h. We have g ′′ y ′′ w ′′ z ′′ u ′′ h ′′ ∈ X ′ * . Moreover since q w ′′ --→ r and q w ′ -→ r are paths in A ′ and ϕ(w ′ ) = ϕ(w ′′ ), w ′ = w ′′ . It follows that w ′ is factor of a word in X ′ * .

Finally, we apply the result obtained in the case of irreducible edge shifts to S ′ and X ′ . It follows that p(A ′ ) divides P (X ′ ) in Z[A ′ ]. By removing the indices of the letters in A ′ (or, equivalently, by applying ϕ), we obtain that p(A) divides P (X) in Z[A].

The following example illustrates Theorem 5 in the case of an irreducible edge shift.

Example 8 If S is the irreducible edge shift described in Figure 4, then

(a) = a 0 0 0 , µ(b) = 0 b 0 0 , µ(c) = 0 0 c 0 .
Let X be the finite S-complete code {aa, ab, ca, cb, bc}. We get µ(X) = a 2 + bc ab ca cb .

We have

p(X) = 1 -a 2 -2bc + b 2 c 2
= (1 + a + bc)(1abc) = (1 + a + bc) p(A).

The next example illustrates the proof of Theorem 5 in the case of an irreducible subshift of finite type which is not an edge shift.

Example 9 If S be the golden mean subshift, then µ(a) = a 0 a 0 , µ(b) = 0 b 0 0 .

Let X be the finite S-complete code X = {aa, ab, aab}. The shift S ′ is recognized by the automaton of Figure 5. Note that S ′ is, up to a renaming of the alphabet, the edge shift of Example 8. We have X ′ = {a 1 a 1 , a 1 b, a 1 a 1 b, a 2 a 1 , a 2 b, a 2 a 1 b}, This phenomenon is linked, in the case of the full shift, to Reutenauer's noncommutative factorization theorem [START_REF] Berstel | Rational Series and their Languages[END_REF]. We do not know whether this theorem holds for shifts of finite type.

The last example below shows an irreducible sofic shift S which is not a shift of finite type. We give an example of an S-complete code X for which there are two ways to find the factorization of p(X).

Example 10 If S is the irreducible sofic shift described in Figure 6, then Let X be the finite S-complete code {aa, ab, ac, ba, bc, cb, ca}. We get µ(X) = a 2 + bc ab + ba ac + ca a 2 + cb .

We have

Figure 1 :

 1 Figure 1: The golden mean system.

Figure 2 :

 2 Figure 2: The even system.

Figure 3 :

 3 Figure 3: A shift of null entropy.

Figure 4 :

 4 Figure 4: An edge shift.

  µ

Figure 5 :

 5 Figure 5: The edge shift S ′ .

  Figure 6: A sofic shift.

p(X) = 1 -

 1 2a 2 -2bc + a 4 + b 2 c 2 -2a 2 bc = (1 -2abc + a 2 )(1 + 2a + a 2bc) = p(A)(1 + 2a + a 2bc).

From 1 -

 1 A 2 = (1 -A)(1 + A), we get Iµ(A 2 ) = (Iµ(A))(I + µ(A)). It follows that det(Iα(A 2 )) = det(Iα(A)) det(I + α(A)).Since det(Iα(A 2 )) = p(X), det(Iα(A)) = p(A), and µ(A) = ( a b c a ), we recover the factorization of p(X):p(X) = det(Iα(A 2 )) = det(Iα(A)) det(I + α(A)) = p(A)(1 + 2a + a 2bc).

Acknowledgment We thank an anonymous reviewer for constructive suggestions which helped us to improve the presentation of this article.