Anthony Sigogne
email: sigogne@univ-mlv.fr

Matthieu Constant
email: mconstan@univ-mlv.fr

Using subcategorization frames to improve French probabilistic parsing

.

Introduction

Dealing with data sparseness is a real challenge for Probabilistic Context-Free Grammar parsers [PCFG], especially when the PCFG grammar is extracted from a small treebank 1 . This problem is also lexical because the richer the morphology of a language is, the sparser the lexicons built from a treebank will be for that language. Nevertheless, the effect of lexical data sparseness can be reduced by word clustering algorithms. Inspired by the clustering method of [START_REF] Koo | Simple semi-supervised dependency parsing[END_REF], [START_REF] Candito | Parsing word clusters[END_REF] have shown that by replacing each word of the corpus by automatically obtained clusters of words, they can significantly improve a PCFG parser on French. Recently, [START_REF] Sigogne | French parsing enhanced with a word clustering method based on a syntactic lexicon[END_REF] proposed a clustering method based on a French syntactic lexicon, the Lexicon-Grammar [LG] [START_REF] Gross | Constructing Lexicon-grammars[END_REF]. This method consists in replacing each word of the corpus by the combination of its part-of-speech tag and its cluster, pre-computed from the lexicon. A 1 Data sparseness implies the difficulty of estimating probabilities of rare rules extracted from the corpus.

cluster corresponds to a class of the lexicon that gathers items sharing several syntactic properties. They applied this method on verbs only and reported significant gains. In this article, we propose a clustering method of verbs and adjectives based on another French lexicon, the Lefff [START_REF] Sagot | The Lefff, a freely available and large-coverage morphological and syntactic lexicon for French[END_REF]. This lexicon does not offer a classification of items as in the LG but for each entry, information about subcategorization frame is available. Clusters of words are now computed by aggregating items that have a similar frame, a frame being reduced to a vector of syntactic functions linked to possible syntactic arguments. In sections 2 and 3, we describe the probabilistic parser and the treebank used in our experiments. In section 4, we describe more precisely previous work on clustering methods. Section 5 introduces the syntactic lexicon, the Lefff, and then we present the clustering approach based on this lexicon. In section 6, we describe our experiments and discuss the obtained results.

Berkeley Parser

The probabilistic parser, used in our experiments, is the Berkeley Parser2 [BKY] [START_REF] Petrov | Learning accurate, compact, and interpretable tree annotation[END_REF]. This parser is based on a PCFG model which is non-lexicalized. The main problem of non-lexicalized context-free grammars is that nonterminal symbols encode too general information which weakly discriminates syntactic ambiguities. The benefit of BKY is to try to solve the problem by generating a grammar containing complex symbols, following the principle of latent annotations introduced by [START_REF] Matsuzaki | Probabilistic CFG with latent annotations[END_REF]. Parameters of the latent grammar are estimated with an algorithm based on Expectation-Maximisation [EM]. In the case of French, [START_REF] Seddah | Adaptation de parsers statistiques lexicalisés pour le franc ¸ais : Une évaluation complète sur corpus arborés[END_REF] have shown that BKY produces state-of-the-art performances.

French Treebank

For our experiments, we used the French Treebank3 [START_REF] Abeillé | Building a treebank for French[END_REF] [FTB]. It is composed of articles from the newspaper Le Monde where each sentence is annotated with a constituent tree. Currently, most papers about parsing of French use a specific variant of the FTB, namely the FTB-UC described for the first time in [START_REF] Candito | Improving generative statistical parsing with semi-supervised word clustering[END_REF]. It is a partially corrected version of the FTB that contains 12.351 sentences and 350.931 tokens with a part-of-speech tagset of 28 tags and 12 nonterminal symbols4 .

Previous work on word clustering

Numerous works used a clustering approach in order to reduce the size of the corpus lexicon and therefore reduce the impact of lexical data sparseness on treebank grammars. Several methods have been described in [START_REF] Candito | Parsing word clusters[END_REF]. The best one, called Clust, consists in replacing each word by a cluster id. Cluster ids are automatically obtained thanks to an unsupervised statistical algorithm [START_REF] Brown | Class-based n-gram models of natural language[END_REF] applied to a large raw corpus. They are computed on the basis of word co-occurrence statistics. Currently, this method permits to obtain the best results on the FTB-UC. Recently, [START_REF] Sigogne | French parsing enhanced with a word clustering method based on a syntactic lexicon[END_REF] described a method, called LexClust, based on a French syntactic lexicon, the Lexicon-Grammar [START_REF] Gross | Constructing Lexicon-grammars[END_REF], that consists in replacing each verbal form of the corpus by the combination of its POS tag and its cluster. These clusters follow the particular classification of entries offered by this lexicon, that aggregates items sharing several syntactic properties (e.g. subcategorization information). For example, a class of this lexicon, called 31R, indicates that all verbs belonging to this class are intransitive. By only modifying the verbs, this approach obtains significant results on the FTB-UC.

5 Word clustering based on a syntactic lexicon 5.1 A syntactic lexicon, the Lefff

The Lefff is a French syntactic and morphological wide-coverage lexicon [START_REF] Sagot | The Lefff, a freely available and large-coverage morphological and syntactic lexicon for French[END_REF] 5 that contains 110.477 lemmatized forms (simple and compound) and 536.375 inflected forms. This lexicon describes for each lemmatized entry a canonical subcategorization frame, composed of all possible arguments of the entry, and a list of possible redistributions from this frame. Inflected entries are built from lemmatized form and for each possible redistribution. For each argument of a subcategorization frame, it is stated the mandatory nature, a syntactic function, syntagmatic productions (pronoun cln, noun phrase np, infinitive phrase sinf,...), and some semantic features (human, abstract,...). A syntactic function takes a value among a set of nine functions, Suj (subject), Obj (direct object), Objà (indirect object introduced by the preposition à), Objde (indirect object introduced by the preposition de), Loc (locative), Dloc (delocative), Att (attribute), Obl and Obl2 (obliques). Figure 1 shows a simplified sample of the Lefff for an entry of the French verb chérir (to cherish). The frame of this entry is composed of two arguments, indicated by the two syntactic functions Suj and Obj. The coverage of the lexicon on the FTB-UC is high, with 99.0% and 96.4% respectively for verbs and adjectives, that are the only two grammatical categories that have available subcategorization frames in the Lefff.

chérir → Suj : (cln|sinf |sn), Obj : (cln|sn)

Figure 1: Sample of the Lefff for an entry of the verb chérir (to cherish).

Word clustering based on the Lefff

The clustering method of verbs and adjectives that we propose in this paper follows the principle of the experiment LexClust. A word in the corpus is replaced by the combination of its part-ofspeech tag and its cluster. These clusters are computed from the Lefff by exploiting subcategorization frames of entries. First, for each lemmatized form of the lexicon, we reduce its frame to the vector of syntactic functions linked to arguments.

If a form appears in several entries (depending on meanings), we merge all vectors into a single one.

Then, clusters are determined by grouping forms that have the same vector. Vectors are composed of syntactic functions taken from a subset of the seven most frequent ones, Suj, Obj, Objà, Objde, Loc, Att et Obl. This subset allows for creating less clusters and improving results. Table 1 shows an example of the clustering process on several verbs of the Lefff. Each verb is associated with its vector of syntactic functions and its cluster. In this example, vectors of verbs abolir and cibler are identical and are composed of a subject and a direct object. Therefore, they belong to the same verb cluster, while other verbs are associated with a distinct cluster. 6 Experiments and results

Evaluation metrics

As the FTB-UC is a small corpus, we used a cross-validation procedure for evaluation. This method consists in splitting the corpus into p equal parts, then we compute training on p-1 parts and evaluations on the remaining part. We can iterate this process p times. This allows us to calculate an average score for a sample as large as the initial corpus. In our case, we set the parameter p to 10. Results on evaluation parts for all sentences are reported using several standard measures, the F 1 score and unlabeled attachment scores. The labeled F 1 score [F1]7 , defined by the standard protocol called PARSEVAL [START_REF] Black | A procedure for quantitatively comparing the syntactic cov-erage of english grammars[END_REF], takes into account the bracketing and labeling of nodes. In order to establish the significance of results between two experiments, we used an unidirectional t-test for two independent samples8 . The unlabeled attachment score [UAS] evaluates the quality of unlabeled dependencies between words of the sentence9 . Punctuation tokens are ignored in all metrics.

Berkeley parser settings

We used a modified version of BKY enhanced for tagging unknown and rare French words [START_REF] Crabbé | Expériences d'analyse syntaxique statistique du franc ¸ais[END_REF] 10 . We can notice that BKY uses two sets of sentences at training, a learning set and a validation set for optimizing the grammar parameters. As in (Candito et al., 2010), we used 2% of each training part as a validation set and the remaining 98% as a learning set. The number of split and merge cycles was set to 5. The random seed was set to 8.

Clustering methods

We evaluated the impact of our clustering method on verbs and adjectives of the FTB-UC (respectively noted Verb and Adj). Those of each training part are replaced by the corresponding cluster and, in order to do it on the evaluation part, we used LGTagger and a lemmatizer. Tagging TAG and lemmatization LEM accuracies of these tools are reported in the Table 3 according to crossvalidation on the FTB-UC. In addition to the overall score for all words in the corpus, F1 score is also reported for verbs and adjectives 11 . First, we can see that verbs are efficiently tagged and lemmatized. About adjectives, there is a greater number of errors (about 5%), and this is mainly because of the ambiguity involved with the past (31% of all errors). LGTagger and Bonsaï lemmatizer according to crossvalidation on the FTB-UC.

Results

The experimental results are shown in the Table 4 12 . The columns #cls and #lex respectively indicate the number of created clusters and the size of the FTB-UC lexicon according to clustering methods. Note that all results are significant compared to the baseline 13 (t-test< 10 -4 ). Absolute gains of experiment Verb are about +0.4 for both F1 and UAS. By just modifying verbs, we can drastically reduce the size of the corpus lexicon. About experiment Adj, despite lower tagging and lemmatization accuracies, clusters allow to obtain gains of about +0.3 for both F1 and UAS. However, combining Adj to Verb has no positive effect compared to Verb and Adj. So as to compare our results with previous work on word clustering, we report, in Table 5, results of the method Clust described in section 4. More-11 We can compute this score because words can be, for example, labeled incorrectly as a verb, or verbs may be labeled incorrectly.

12 All experiments have a tagging accuracy of about 97%. We can see that Clust obtains the best scores, with an absolute gain of +0.9 for F1 and +0.4 for UAS compared to Verb. Nevertheless, we obtain similar results to Clust when our verb clusters are combined with method Clust, applied on all other words of the corpus (t-test>0.2). Therefore, it would mean that verb clusters computed from a lexicon are as powerfull as clusters from a statistical model.

Conclusion

In this article, we have shown that by using information about verbs (and to a lesser extent, adjectives) from a syntactic lexicon, the Lefff, we are able to improve performances of a statistical parser based on a PCFG grammar. In the near future, we plan to reproduce experiments with other grammatical categories like nouns available in other French lexicons.

Table 1 :

 1 Table 2 shows a similar example for adjective clusters. Verb clusters obtained from the Lefff.

	Verb	Vector	Cluster
	abolir (to abolish)	Suj, Obj	1
	cibler (to target)	Suj, Obj	1
	prouver (to prove)	Suj, Obj, Objà, Obl 2
	gratifier (to gratify) Suj, Obj, Objde	3
	Adjective	Vector	Cluster
	celtique (celtic)	Suj, Objde, Objà 1
	censuré (censored) Suj, Obl2	2
	chanceux (lucky)	Suj, Objde, Objà 1
	lavé (washed)	Suj, Obj, Obl2	2

Table 2 :

 2 Adjective clusters obtained from the Lefff. Bonsaï tool 6 which is based on the Lefff and some heuristics in case of ambiguities.

	However, this approach requires a POS tagger and
	a lemmatizer in order to analyze a raw text (clus-
	ters being determined from lemmatized forms).
	Therefore, we chose one of the best tagger for
	French called LGTagger (Constant and Sigogne,
	2011) which is based on a Conditional Random
	Field probabilistic model. Lemmatization is made

Table 3 :

 3 Tagging and lemmatization accuracies of

		All	Verbs Adjectives
	TAG	97.75 97.83 94.80
	LEM 96.77 97.15 95.84

Table 4 :

 4 13 Baseline experiment consists in training and evaluating BKY on FTB-UC with original words. Results from cross-validation evaluation according to our clustering methods.over, we tried some combination of methods Verb, Adj and Clust. In this case, Clust only replaces words of other grammatical categories.

		#cls #lex	F1	UAS
	Baseline	-	27.143 84.03 89.58
	Verb	96	20.567 84.44 89.96
	Adj	16	23.982 84.30 89.79
	Verb+Adj 112 17.108 84.42 89.92
		#cls	#lex	F1	UAS
	Verb	96	20.567 84.44 89.96
	Clust	1000 1.987	85.25 90.42
	Verb+Clust	1096 2.186	85.13 90.25
	Verb+Adj+Clust 1112 730	84.93 89.98

Table 5 :

 5 Results from cross-validation evaluation according to our clustering methods.

http://code.google.com/p/ berkeleyparser/

Proceedings of KONVENS 2012 (Main track: poster presentations), Vienna, September 20, 2012

Available under licence at http:// www.llf.cnrs.fr/Gens/Abeille/ French-Treebank-fr.php

There are also 7 possible syntactic functions attached to nonterminal nodes. Those annotations were removed for our experiments.

http://atoll.inria.fr/ ˜sagot/lefff. html

http://alpage.inria.fr/statgram/ frdep/

Evalb tool available at http://nlp.cs.nyu.edu/ evalb/

Dan Bikel's tool available at http://www.cis. upenn.edu/ ˜dbikel/software.html

This score is computed by automatically converting constituent trees into dependency trees. The conversion procedure is made with the Bonsaï tool.

10 Available in the Bonsaï package.


Jean Berstel

Clelia De Felice

Dominique Perrin

Giuseppina Rindone

On the groups of codes with empty kernel

An internal factor of a word x is a word v such that x = uvw for some nonempty words u, w. The kernel of a set X of words is the set of words of X which are internal factors of words of X. Let ϕ be the syntactic morphism of the submonoid X * generated by X. We prove that if X is a code with empty kernel, the groups contained in the image by ϕ of the complement of the set of internal factors of the words of X are cyclic. This generalizes a result announced by Schützenberger in 1964.

Introduction

Groups contained in finite monoids play an important role in their description. In particular, the finite monoids containing only groups in a given variety of finite groups form a variety of finite monoids. These varieties have been studied in several cases including the trivial variety of groups, corresponding to the variety of aperiodic monoids. The study of groups contained in syntactic monoids of sets of words is an important chapter of automata theory. To a given variety of finite monoids corresponds a family of rational sets called a * -variety(see [START_REF] Eilenberg | With two chapters ("Depth decomposition theorem[END_REF] or [START_REF] Lallement | Semigroups and combinatorial applications[END_REF] for an introduction to this subject). We will prove here results which show that the groups in the syntactic monoids of some sets are cyclic and thus belong to the variety of Abelian groups.

We actually prove here a result (Theorem 1 below) which is a generalization of the fact that the group of a semaphore code is cyclic. The starting point of this research is the article On the synchronizing properties of certain prefix codes published by Schützenberger in 1964 [START_REF] Schützenberger | On the synchronizing properties of certain prefix codes[END_REF]. This paper presents a family of maximal prefix codes called J -codes, that we call semaphore codes. The main result of [START_REF] Schützenberger | On the synchronizing properties of certain prefix codes[END_REF] is that a semaphore code is always of the form X n where X is a synchronized semaphore code and n ≥ 1. Two proofs are presented of this result in [START_REF] Schützenberger | On the synchronizing properties of certain prefix codes[END_REF]. The first one is combinatorial and rather hard to follow. The second one uses intermediary results which are interesting in their own (this is the proof presented in [START_REF] Berstel | Codes and Automata[END_REF]). First, it is proved ( [START_REF] Schützenberger | On the synchronizing properties of certain prefix codes[END_REF], Remark 1) that the group of a semaphore code is a regular permutation group. Next, it is proved ( [START_REF] Schützenberger | On the synchronizing properties of certain prefix codes[END_REF], Property 2) that if the group G of a maximal prefix code X is regular (the statement says Abelian but the proof uses only the fact that it is regular), then there is a decomposition X = Y • Z • T such that Y, T are synchronizing and Z is a group code with G(Z) = G. A third result ([5], Remark 2) shows that if X is a semaphore code such that X = Y • Z • T with Z a regular group code, then X = U n with U a synchronized semaphore code and n ≥ 1. This implies that the group of a semaphore code is cyclic since G(U ) is trivial and G(X) = Z/nZ. At the end of the paper, it is claimed that all groups in the syntactic monoid of X * which are not included in the image of the set of factors of X are cyclic, but the proof is not correct.

We prove here a generalization replacing semaphore codes by codes with empty kernel. An internal factor of a word x is a word v such that x = uvw for some nonempty words u, w. The kernel of a set of words X ⊂ A + is the set of words of X which are internal factors of words of X. In particular, a semaphore code has empty kernel but codes with empty kernel are more general since they need not be prefix nor maximal. Let X be a code with empty kernel and let F be the set of internal factors of words of X. Let ϕ be the morphism from A * onto the transition monoid of an unambiguous automaton A = (Q, 1, 1) recognizing X * . We prove that any group G contained in ϕ(A * \ F ) is cyclic (Theorem 1). We deduce from this result a closure property of the * -variety corresponding to the variety of monoids containing only Abelian groups (Theorem 2).

The article is organized as follows. In the first section, we introduce preliminary results and recall some definitions about codes and unambiguous automata. We prove in particular a result on sets of interpretations of a word with respect to a code with empty kernel (Lemma 2). In Section 3, we prove the main result (Theorem 1) and list some corollaries. We illustrate these results on several examples. They were computed with the help of the software Semigroupes [START_REF] Froidure | Algorithms for computing finite semigroups[END_REF] available at http://www.liafa.jussieu.fr/ ~jep/Semigroupe2.0/semigroupe2.html. In the last section, we use Theorem 1 to prove a closure property of the * -variety V of recognizable sets such that their syntactic monoid contains only Abelian groups. In fact, we prove that if X is a code with empty kernel which is in V, then X * is also in V (Theorem 2).

Preliminaries

In this section, we introduce the notions used in the paper. For a more detailed exposition, see [START_REF] Berstel | Codes and Automata[END_REF].

Codes and interpretations

Let A be a finite alphabet. We denote by A * the free monoid on A and by A + the free semigroup on A. The empty word is denoted by 1.

Codes. A code is a set X ⊂ A + such that x 1 • • • x n = y 1 • • • y m with x i , y j ∈ X implies n = m and x i = y i for 1 ≤ i ≤ n.

When X ⊂ A + is a code, the submonoid X * generated by X is stable. This means that, for any words u, v, w in A * , if u, uv, vw and w are in X * then v is also in X * .

A set X ⊂ A * is said to be dense if any word in A * is a factor of a word in X. A set which is not dense is said to be thin.

A set X ⊂ A * is complete if X * is dense.
A prefix code is a set X ⊂ A + such that no word of X is a prefix of another word of X. The definition of a suffix code is symmetrical. A bifix code is a set which is simultaneously a prefix code and a suffix code.

An infix code is a set X ⊂ A + such that no word of X is a factor of another word of X.

A semaphore code is a set of the form A * S \ A * SA + for some nonempty set S ⊂ A + . A semaphore code is prefix by definition. Conversely, it can be shown that a prefix code X ⊂ A + is a semaphore code if and only if A * X ⊂ XA * . A semaphore code is thin and complete.

For any semaphore code X ⊂ A + , the set Y = X \ A * X is an infix code.

An internal factor of a word x ∈ A * is a word v ∈ A * such that x = uvw for some nonempty words u, w. The kernel of a set of words X ⊂ A + is the set of words of X which are internal factors of words of X.

Examples of codes with empty kernel include infix codes and semaphore codes.

Factorizations. A factorization of a word w ∈ A * is a sequence (u 1 , u 2 , . . . , u n ) with n ≥ 1, u i ∈ A + for 2 ≤ i ≤ n -1 and u 1 , u n ∈ A * such that w = u 1 u 2 • • • u n .
Thus the terms of a factorization are all nonempty, except possibly the first and the last one.

The

content of a sequence α = (u 1 , u 2 , . . . , u n ) of words u i ∈ A * is the word w = u 1 u 2 • • • u n . We denote w = c(α).
For a factorization α = (u 1 , u 2 , . . . , u n ), we denote

P (α) = {u 1 , u 1 u 2 , . . . , u 1 u 2 • • • u n-1 }.
We say that β refines α, denoted α < β, if P (α) ⊂ P (β). The supremum of two factorizations

α = (u 1 , u 2 , . . . , u n ) and β = (v 1 , v 2 , . . . , v m ) of a word w, denoted α∨β, is the unique factorization γ = (w 1 , w 2 , • • • , w p ) of w such that P (γ) = P (α) ∪ P (β).
Example 1 The word w = ab has 8 distinct factorizations represented in Figure 1 with the refinement order indicated vertically.

(ab)

(1, ab) (a, b) (ab, 1) (1, a, b) (1, ab, 1) (a, b , 1) (1, a, b, 1)
Figure 1: The 8 factorizations of w = ab.

Two factorizations α and β of a word w are adjacent if P (α

) ∩ P (β) = ∅. Thus α = (u 1 , u 2 , . . . , u n ) and β = (v 1 , v 2 , . . . , v m ) are adjacent if there exists i, j with 1 ≤ i < n and 1 ≤ j < m such that u 1 • • • u i = v 1 • • • v j and u i+1 • • • u n = v j+1 • • • v m . Two factorizations which are not adjacent are disjoint.
Interpretations. Let X ⊂ A + be a code. Let P be the set of proper prefixes of the words of X and let S be the set of proper suffixes of the words of X. An interpretation of a word w ∈ A * with respect to X is a factorization α = (s, x 1 , x 2 , . . . , x n , p) of w such that s ∈ S, n ≥ 0, x i ∈ X and p ∈ P . p x 1

x 2 q r y 1 y 2 s

Figure 2: Two adjacent interpretations

Thus an interpretation α is made of three parts: a proper suffix s of X denoted s α , a possibly empty sequence (x 1 , x 2 , • • • , x n ) of words of X denoted f α and a proper prefix p of X denoted p α . In particular, an interpretation is a factorization with at least two terms.

Two interpretations of a word w are said to be adjacent (resp. disjoint) if the corresponding factorizations are adjacent (resp. disjoint) (see Figure 2). Two interpretations α, β of a word w are connected if w = uxv for some words u, v ∈ A * and x ∈ X * such that u ∈ P (α) and ux ∈ P (β).

Note that α, β are connected if and only if there exists an interpretation γ of w which is adjacent to α and β (see Figure 3). Thus adjacent interpretations are connected. The converse is not true in general as shown by the following example.

Example 2 Let A = {a, b} and let X = {aab, bbb, bba, baa, aabbb}. The word w = aabbba has two disjoint interpretations α = (aa, bbb, a) and β = (1, aab, bba, 1). They are connected since both are adjacent to γ = (1, aabbb, a). Two interpretations of a word which are not connected are said to be independent.

For each set of interpretations of a word w, one may consider their supremum, which is a factorization of w. Let (u 1 , u 2 , . . . , u m ) be the supremum of a set I of interpretations of a word w. Then for each k with 1 ≤ k < m there is an element of I which refines the factorization

(u 1 • • • u k , u k+1 • • • u m ).
Residuals. For a word u ∈ A * and a set X ⊂ A * , we denote u -1 X = {v ∈ A * | uv ∈ X}. In particular, when X = {w} has just one element, we write u -1 w instead of u -1 {w}. If u -1 w is not empty, we identify the set u -1 w with the word v such that w = uv.

For a letter a ∈ A and a sequence α = (u 1 , u 2 , . . . , u n ) of words u i ∈ A * , we define a sequence of words a -1 α as follows. First a -1 α = ∅ if n = 0. Next, for n ≥ 1, we define by induction on n

a -1 α =      a -1 (u 2 , . . . , u n ) if u 1 = 1 (a -1 u 1 , u 2 , . . . , u n ) if u 1 ∈ aA * ∅ otherwise.
Let α be a factorization of a word w ∈ A + and let a ∈ A be a letter. Then a -1 α and a -1 w are nonempty if and only if a is the first letter of w. In this case a -1 α is a factorization of a -1 w.

Example 3

We have already seen that the word w = ab has 8 distinct factorizations (Example 1) represented in Figure 4 on the left with the refinement order. The 4 distinct factorizations of the word a -1 w = b are represented on the right.

(ab) (1, ab) (a, b) (ab, 1) (1, a, b) (1, ab, 1) (a, b, 1)
(1, a, b, Let α be an interpretation of a nonempty word w ∈ A + with respect to a code X and let a be the first letter of w. Suppose that s α = 1 or that f α is not empty. Then a -1 α is an interpretation of a -1 w. Indeed, let α = (s, x 1 , x 2 , . . . , x n , p). If s = 1, then a -1 α = (a -1 s, x 1 , x 2 , . . . , x n , p). Next, if s = 1 and n ≥ 1, then a -1 α = (a -1 x 1 , x 2 , . . . , x n , p).

Lemma 1 Let α, β, be two independent interpretations of a nonempty word w. Let a be the first letter of w and let w ′ = a -1 w, α ′ = a -1 α, β ′ = a -1 β. We assume that s α = 1 or f α is not empty and that s β = 1 or f β is not empty. Then α ′ , β ′ are independent interpretations of w ′ .

Proof. The condition guarantees that α ′ and β ′ are interpretations of w ′ . Suppose that α ′ , β ′ are connected. Let u, v ∈ A * and x ∈ X * be such that w ′ = uxv with u ∈ P (α ′ ) and ux ∈ P (β ′ ). Then w = auxv with au ∈ P (α) and aux ∈ P (β) implies that α and β are connected, a contradiction.

Let I be a set of n interpretations of a word w. Let (u 1 , u 2 , . . . , u m ) be the supremum of the elements of I. For α ∈ I, set w = sxp with s = s α , x = c(f α ) and p = p α . There are unique integers i, j with 1 ≤ i ≤ n and i ≤ j < m such that

s = u 1 • • • u i , x = u i+1 • • • u j , p = u j+1 • • • u m . (1)
We define λ(α, I)

= i -1, µ(α, I) = j -i, ν(α, I) = m -j -1. (2)
Thus λ(α, I), µ(α, I) and ν(α, I) are the number of words u k which compose each element of the interpretation, not taking in account the (possibly empty) first and last one.

A factorization (u 1 , u 2 , . . . , u m ) of a word w is said to be n-periodic with respect to a code X if for any r, ℓ with 1 ≤ ℓ ≤ r ≤ m -1, one has u ℓ+1 • • • u r ∈ X if and only if rℓ = n. Thus, in other terms, the factorization is n-periodic if and only if the number of consecutive nonempty factors u i with 2 ≤ i ≤ m -1 whose product is in X is constant and equal to n.

A set I of n interpretations of a word w with respect to a code X is said to be cyclic if the supremum (u 1 , u 2 , . . . , u m ) of the n interpretations is n-periodic with respect to X (see Figure 5).

Let I be a set of n interpretations of a word w with respect to a code X. If I is cyclic, then for each α ∈ I, µ(α, I) ≡ 0 mod n

Indeed, let σ = (u 1 , u 2 , . . . , u m ) be the supremum of the elements of I. Since I is cyclic, the factorization σ is n-periodic. Thus, each word of X which appears in the content of f α is a product of n consecutive nonempty elements of σ. Note that if the set I is cyclic, the elements of I are pairwise independent. Let indeed (u 1 , . . . , u m ) be the supremum of the elements of I. Let α be an element of I and set

s α = u 1 • • • u i with 1 ≤ i < n. Then for i ≤ r ≤ m -1, u 1 • • • u r ∈ P (α) implies u i+1 • • • u r ∈ X * and thus r ≡ i mod n. Thus u 1 • • • u r ∈ P (α) implies r -1 ≡ λ(α, I) mod n.
Let then α, β ∈ I be connected. By definition, we have w = uxv for some words u, v ∈ A * and x ∈ X * such that u ∈ P (α) and ux ∈ P (β). Set u = u 1 • • • u ℓ and x = u ℓ+1 • • • u r . Then, by the above argument, we have λ(α, I) ≡ ℓ -1 mod n and λ(β, I) ≡ r -1 mod n. Since x ∈ X * , we have also rℓ ≡ 0 mod n. Finally, we obtain λ(α, I) ≡ λ(β, I) mod n and thus λ(α, I) = λ(β, I). In the same way ν(α, I) = ν(β, I) and thus α = β. Example 4 Let A = {a, b} and X = {aab, abaa, abab, baba}. The set X is a code with empty kernel. The word w = ababaababa has the set I of 3 interpretations (1, abab, aab, aba), (a, baba, abab, a) and (ab, abaa, baba, 1). The supremum of these interpretations is the 3-periodic factorization (1, a, b, ab, a, a, b, ab, a, 1) of w with m = 10 factors. Thus I is cyclic.

u 1 u 2 u 3 u m-1 u m
We will use the following result.

Lemma 2 Let X ⊂ A + be a code with empty kernel. Any set of independent interpretations of a word with respect to X is cyclic.

Proof. Let w be a word with n pairwise independent interpretations. The proof is by induction on the length of w. It is true for the empty word since in this case there is at most one interpretation, which is (1, 1) and the property holds trivially. Assume that the property holds for the words shorter than a nonempty word w. Let I be a set of n pairwise independent interpretations of w. Set I = {α 0 , α 1 , . . . , α n-1 } in such a way that s αi is a proper prefix of s αi+1 for 0 ≤ i ≤ n -2. We first consider the case where s α0 = 1 or f α0 is not empty.

In this case, set w = aw ′ with a ∈ A and w ′ ∈ A * . By Lemma 1 the set

I ′ = {a -1 α | α ∈
I} is a set of n pairwise independent interpretations of w ′ . By induction hypothesis the set I ′ is cyclic and the supremum µ = (u 1 , . . . , u m ) of the elements of I ′ is n-periodic.

If s α0 = 1, then the sequence ν = (au 1 , . . . , u m ) is the supremum of the elements of I. Since ν is also n-periodic, the set I is cyclic.

If s α0 = 1 and f α0 is nonempty, the sequence ν = (1, au 1 , . . . , u m ) is the supremum of the elements of I. We verify that ν is n-periodic.

Since µ = (u 1 , . . . , u m ) is n-periodic, one has u ℓ+1 • • • u r ∈ X if and only if r -ℓ = n for 1 ≤ ℓ ≤ r ≤ m -1.
We have to show that additionally, au

1 u 2 • • • u r ∈ X if and only if r = n.
Let us prove that we cannot have au 1 u 2 • • • u r ∈ X with r < n. Indeed, since X is a code with empty kernel, no word x ∈ X can be a proper prefix (or a proper factor) of s αi for i ∈ {1, . . . , n-1} (otherwise x would be proper factor of zs αi , where z ∈ A + is such that zs αi ∈ X). As a consequence, au 1 u 2 • • • u r = s αr , r ∈ {1, . . . , n -1} (see also Equation ( 1)) and au

1 u 2 • • • u r = s αr ∈ X for r < n -1. Furthermore, if au 1 u 2 • • • u n-1 = s αn-1 ∈ X, γ = (1, s αn-1 f αn-1 , p αn-1
) would be adjacent to α 0 and to α n-1 , a contradiction. Let us prove that we cannot have au

1 u 2 • • • u r ∈ X with r > n. Notice that u 2 • • • u n+1 ∈ X (I ′ is cyclic) and so, u 2 • • • u n+1 is the first term in f α1 . Furthermore, u i = 1 for i ∈ {2, . . . , m -1}, since µ is a factorization. Thus, we cannot have au 1 u 2 • • • u r ∈ X with n + 1 < r ≤ m -1 since u 2 • • • u n+1 ∈ X
and X is a code with empty kernel and we cannot have

au 1 u 2 • • • u n+1 ∈ X since γ = (1, s α1 f α1 , p α1
) would be adjacent to α 0 and to α 1 . Finally, since

au 1 u 2 • • • u n is the first term in the sequence f α0 , we have au 1 u 2 • • • u n ∈ X.
Suppose finally that s α0 = 1 and f α0 is empty. In this case w = p α0 and thus the sequences f αj for j ∈ {1, . . . , n -1} are empty. Indeed, otherwise their terms would be proper factors of p α0 y, where y ∈ A + is such that p α0 y ∈ X (as s αj = 1 for j ∈ {1, . . . , n -1}). Consequently, α j = (s αj , p αj ), P αj = {s αj }, 0 ≤ j ≤ n -1, and the supremum of the set

I is (u 0 , . . . , u n-1 , u n ), with u 0 • • • u j = s αj , 0 ≤ j ≤ n -1, and u n = p αn-1 . In order to conclude that this factorization is n-periodic we have to prove that u 0 • • • u j = s αj ∈ X, for 0 < j ≤ n -1. Now, we cannot have u 0 • • • u j = s αj ∈ X, for 0 < j < n -1, since otherwise s αj ∈ X would be proper factor of zs αn-1 , where z ∈ A + is such that zs αn-1 ∈ X, nor can we have u 0 • • • u n-1 = s αn-1 ∈ X, since otherwise γ = (1, s αn-1 , p αn-1
) would be adjacent to α 0 and to α n-1 , a contradiction.

Observe that Lemma 2 is not true for a set of disjoint interpretations (instead of independent) as shown by the following example.

Example 5 Let A = {a, b} and let X = {aab, bbb, bba, baa, aabbb} as in Example 2. The code X has empty kernel. The word w = aabbba has two disjoint interpretations α = (aa, bbb, a) and β = (1, aab, bba, 1). The supremum of α, β is the factorization (1, aa, b, bb, a, 1). It is not 2-periodic since aabbb is in X although it is a product of three terms of the factorization.

Groups, monoids and automata

We now give definitions concerning groups, monoids and automata. Again, for a more detailed presentation, see [START_REF] Berstel | Codes and Automata[END_REF].

Permutation groups. Let us recall some terminology about permutation groups (see also [START_REF] Wielandt | Finite permutation groups[END_REF]). Let G be a permutation group on a set R. We denote the action of G on R on the right. Thus an element g of G maps each r ∈ R to some rg ∈ R. The degree of G is the cardinality of the set R. The order of G is the cardinality of G. The orbits of G are the classes of the equivalence on R defined by p ≡ q if there exists g ∈ G such that pg = q. The group G is said to be transitive if there is only one orbit.

A permutation group is called regular if no element distinct from the identity has a fixpoint. All orbits in a regular group have the same cardinality equal to the order of the group. In particular, the order of a regular group is a divisor of its degree. A finite permutation group is cyclic and regular if and only if it is generated by a permutation composed of disjoint cycles of the same length. As mentionned in the introduction, a transitive permutation group which is Abelian is regular (see [START_REF] Wielandt | Finite permutation groups[END_REF], Proposition 4.4). Indeed, suppose that rg = r for some r ∈ R and g ∈ G. Let us show that sg = s for any s ∈ R. Since G is transitive, there is some h ∈ G such that r = sh. Since G is Abelian, hg = gh and thus shg = sh implies sgh = sh. Since h is a permutation on R, this implies sg = s. Thus g is the identity and this shows that G is regular.

Ideals in monoids.

A group in a monoid M is a subset G of M such that the operation of M gives to G a group structure. More precisely, a group in M is a subset G of M containing an idempotent e, such that for any g, h ∈ G one has gh ∈ G and such that for any g ∈ G there is some h ∈ G such that gh = hg = e.

For any idempotent e in a monoid M , there is a largest group G contained in M which has e as neutral element, called the maximal group containing e. It is the set of all m ∈ M such that em = me = m and such that there exists n ∈ M such that mn = nm = e.

An ideal of a monoid M is a nonempty subset I of M such that for any m, n ∈ M and x ∈ I, one has mxn ∈ I. If I is an ideal and G is a group contained in M , then either G ∩ I = ∅ or G ⊂ I. Indeed, let x ∈ G ∩ I. Then for any g ∈ G, we have g = x -1 xg and thus g is in I.

Automata. Given an alphabet A, we denote by A = (Q, I, T ) an automaton with Q as set of states, I as set of initial states and T as set of terminal states. The automaton is defined by its set of edges

E ⊂ Q × A × Q. The automaton is said to be finite if the set E is finite. A path in A is a sequence p 0 a1 → p 1 • • • an → p n of consecutive edges. Its label is the word w = a 1 • • • a n . The path is null if the sequence is empty, that is if w = 1.
We denote by L(A) the set of labels of paths from I to T . We say that A recognizes the set L(A). A set X ⊂ A * is said to be recognizable if it can be recognized by a finite automaton.

The automaton A = (Q, I, T ) is trim if for any state q ∈ Q, there is a path from I to q and from q to T . An automaton is called simple if (i) it is trim, (ii) there is a unique initial state, a unique terminal state and they are equal.

Let A = (Q, 1, 1) be a simple automaton. A path p w → q in A is said to be simple if it is not the null path (that is w = 1) and if for any factorization p u → r v → q of the path into nonnull paths, one has r = 1.

We denote by ϕ A the morphism from A * into the monoid of relations on the set Q defined by

ϕ A (w) = {(p, q) ∈ Q × Q | p w → q}.
For a word w, we will often talk of ϕ A (w) as the relation on Q defined by w. The monoid M = ϕ A (A * ) is a monoid of relations on Q which is called the transition monoid of the automaton A. We denote by 1 the identity relation and by 0 the empty relation.

An automaton A = (Q, I, T ) is deterministic if it has a unique initial state and for any p ∈ Q and a ∈ A, there is at most one q ∈ Q such that (p, a, q) is an edge of A.

For any set X ⊂ A + the minimal automaton of X is the deterministic automaton A = (Q, i, T ) defined as follows. The elements of Q are the classes of the equivalence on A * defined by u ≡ v if for any w ∈ A * , one has uw ∈ X if and only if vw ∈ X. For each a ∈ A there is an edge with label a from the class of a word u to the class of ua. The initial state is the class of the empty word. The terminal states are the classes included in X. The transition monoid of the minimal automaton is the syntactic monoid of X.

The automaton is unambiguous if for any p, q ∈ Q and w ∈ A * there is at most one path from p to q labeled w. A deterministic automaton is clearly unambiguous.

For any code X ⊂ A + , there exists a simple unambiguous automaton recognizing X * . It can be obtained as follows. Let A = (Q, I, T ) be a trim unambiguous automaton recognizing X. Let E be the set of edges of A. Let ω ∈ Q be a new state. Let B = (Q ∪ ω, ω, ω) be the automaton with edges formed of the edges of A plus the edges (ω, a, q) such that (i, a, q) ∈ E for some i ∈ I, the edges (p, a, ω) such that (p, a, t) ∈ E for some t ∈ T and the edges (ω, a, ω) such that (i, a, t) ∈ E for some i ∈ I and t ∈ T . Then the trim part of B is a simple unambiguous automaton denoted A * which recognizes X * . Moreover, X is the set of labels of simple paths in A * .

When X is prefix, provided the automaton A is deterministic, the automaton A * is also deterministic. Moreover, the minimal automaton of X * is simple.

Unambiguous monoids of relations. Let m be a relation between two sets P and Q and let n be a relation between two sets Q and R. The product mn is unambiguous if for any (p, r) ∈ P × R there is at most one q ∈ Q such that (p, q) ∈ m and (q, r) ∈ n. A monoid M of relations on a set Q is unambiguous if for any m, n ∈ M the product mn is unambiguous. When A is an unambiguous automaton, the monoid M = ϕ A (A * ) is unambiguous.

A monoid M of relations on a set Q is transitive if for any p, q ∈ Q there exists an element m ∈ M such that (p, q) ∈ m (note that this term is in agreement with the notion of a transitive permutation group).

The rank of a relation m between sets P and Q is the minimal cardinality of a set R for which there exist relations u on P × R and v on R × Q such that m = uv and such that the product uv is unambiguous. Thus, the rank of m is zero if and only if m is the empty relation.

Let M be a transitive unambiguous monoid of relations containing relations of finite rank and not containing the empty relation. Let r(M ) be the minimal rank of the elements of M . The set of relations of rank r(M ) is the minimal ideal of M (see [START_REF] Berstel | Codes and Automata[END_REF] Theorem 9.3.15). It is the intersection of all the ideals of M .

Let M be an unambiguous monoid of relations on a set Q. We denote by Fix(m) the set of fixpoints of an element m ∈ M . It is the set of q ∈ Q such that (q, q) ∈ m. The rank of an idempotent is equal to the number of its fixpoints (see [START_REF] Berstel | Codes and Automata[END_REF], Proposition 9.3.6).

The following characterization of idempotents is useful (see [START_REF] Berstel | Codes and Automata[END_REF] for more details).

Lemma 3 Let M be an unambiguous monoid of relations on a set Q. An element m ∈ M is idempotent if and only if the following condition is satisfied: For any p, q ∈ Q, one has (p, q) ∈ m if and only if there is a fixpoint r of m such that (p, r), (r, q) ∈ m.

Proof. The condition is sufficient. Indeed, it implies directly that m ⊂ m 2 . Conversely, suppose that (p, q) ∈ m 2 . Let r ∈ Q be such that (p, r), (r, q) ∈ m. By the condition, there are s, t ∈ Fix(m) such that (p, s), (s, r), (r, t), (t, q) ∈ m. Thus we have (p, r), (p, t) ∈ m 2 and (r, q), (t, q) ∈ m. By unambiguity, this implies r = t. Thus r ∈ Fix(m) and (p, q) is in m by the condition. Conversely, suppose that m is idempotent. Let p, q ∈ Q be such that (p, q) ∈ m. Since m = m 3 , there exist r, s ∈ Q such that (p, r), (r, s), (s, q) ∈ m. Since m = m 2 we have also (r, q) ∈ m and (p, s) ∈ m. By unambiguity, we obtain r = s and thus r ∈ Fix(m).

Let M be an unambiguous monoid of relations on a set Q. Let G ⊂ M be a group in M and let e be the neutral element of G. The group G is faithfully represented as a permutation group on the set R = Fix(e). This means that the restriction of the elements of G to R × R is an isomorphism from G onto a permutation group on R. We will often, by abuse of notation, identify the group G with this permutation group (although the elements of G are relations on Q). Since Card(R) is equal to the rank of e, the group G is a a permutation group of degree equal to the rank of e.

For r ∈ Fix(e) and g ∈ G, we denote by rg the image of r by the permutation defined by g on R. It is the unique fixpoint s ∈ R such that (r, s) ∈ g. Thus the permutation defined by g on R is the restriction of the relation g to R × R. It is thus contained in the relation g.

For an unambiguous automaton A on a set Q of states and a word w, we say that w contains a permutation π on R ⊂ Q if π is the restriction of ϕ A (w) to R × R. When R is finite and is the set of fixpoints of an idempotent e, the permutation π is an element of the maximal group G containing e. Set indeed m = eϕ A (w)e. Then em = me = m. Moreover, since R is finite there is an integer k ≥ 1 such that the restriction to R of m k is the identity and thus m k = e. This shows that m k-1 is the inverse of m in G.

Let M be a transitive unambiguous monoid of relations not containing the empty relation. Let I be the minimal ideal of M , which is formed of the elements of M of rank r(M ). The set I is a union of equivalent transitive groups of degree r(M ) (see [START_REF] Berstel | Codes and Automata[END_REF], Theorem 9.3.15). The Suschkevitch group of M is any of them.

Let X ⊂ A + be a code and let A be a simple unambiguous automaton recognizing X * . Some of the groups in ϕ A (A * ) do not depend on the choice of the unambiguous automaton. Indeed, let F be the set of factors of the words of X. If A and B are two simple unambiguous automata such that X * = L(A) = L(B), any group contained in ϕ A (A * \ F ) is equivalent to a group in ϕ B (A * \ F ) (see [START_REF] Berstel | Codes and Automata[END_REF], Proposition 9.5.1). In particular, this is true for the group G(X) of the code X, which is the Suschkevitch group of the monoid of transitions of any simple unambiguous automaton recognizing X * (see [START_REF] Berstel | Codes and Automata[END_REF], Proposition 9.5.2).

We will use later the following elementary results (see [START_REF] Berstel | Codes and Automata[END_REF]). The first one is a property of unambiguous automata.

Proposition 1 Let X ⊂ A + be a code and let A be a simple unambiguous automaton recognizing X * . Let G be a group which meets ϕ A (X * ).

Then G ∩ ϕ A (X * ) is a subgroup of G.
Proof. We use the fact that the submonoid N = ϕ A (X * ) is stable. Indeed, let u be in G ∩ ϕ A (X * ). Let e be the neutral element of G.

Then ue = eu = u implies that e ∈ N . Next, if v is the inverse of u in G, then uv, vu ∈ N imply v ∈ N . Thus G ∩ N is a subgroup of G.
The second one is a classical property of monoids.

Proposition 2 Let G be a group in a monoid M . Let m, n ∈ M be such that mn ∈ G. Then nGm is a group isomorphic to G.

Proof. Since mn ∈ G, we have nGmnGm ⊂ nGm. Next e = n(mn) -1 m ∈ nGm is an idempotent. Thus nGm is a monoid. For any g ∈ G, the element h = n((mn) -1 g -1 (mn) -1 )m is the inverse of ngm. Thus nGm is a group and finally, the map f : G → nGm defined by f (g) = n(mn) -1 gm is an isomorphism from G onto nGm.

Main result

We will prove the following result.

Theorem 1 Let X ⊂ A + be a code with empty kernel and let F be the set of internal factors of the words of X. Let A be a simple unambiguous automaton recognizing X * . Any group contained in ϕ A (A * \ F ) is a finite cyclic group which is regular.

Observe that that since ϕ

A (A * \ F ) is an ideal, for a group G contained in ϕ A (A * ), the condition G ⊂ ϕ A (A * \ F ) is equivalent to G ∩ ϕ A (A * \ F ) = ∅.
Observe also that the groups above are not always transitive (see Example 8). Before giving the proof, we list some corollaries. The following statement is the result appearing at the end of [START_REF] Schützenberger | On the synchronizing properties of certain prefix codes[END_REF] with an incorrect proof.

Corollary 1 Let X ⊂ A + be a semaphore code and let F be the set of internal factors of the words of X. Let A be a simple deterministic automaton recognizing X * . Any group contained in ϕ A (A * \ F ) is a finite cyclic group which is regular.

Proof. The result follows directly from Theorem 1 since a semaphore code has empty kernel.

The second corollary concerns the group G(X) which is a finite transitive permutation group for any thin complete code (thus the fact that such a group is cyclic implies that it is regular).

Corollary 2 Let X be a semaphore code. Then the group G(X) is cyclic.

Proof. Let F be the set of internal factors of the words of X. Let A be a simple deterministic automaton recognizing X * . Set ϕ = ϕ A and M = ϕ(A * ). Since X is a semaphore code, it is thin and complete. Thus M has elements of finite rank and does not contain the empty relation (see [START_REF] Berstel | Codes and Automata[END_REF], Theorem 9.4.1). Let e be an idempotent of minimal rank in M . Since the minimal ideal of M is the set of elements of minimal rank, e belongs to the minimal ideal. Then G = eM e is the maximal group containing e. Thus it is the Suschkevitch group of the monoid M . Since the elements of G belong to the minimal ideal of M , the group G is contained in the ideal ϕ(A * \ F ) and the result follows.

Corollary 3 Let X ⊂ A + be a finite code with empty kernel. Let A be a simple unambiguous automaton recognizing X * . Then any group in ϕ A (A * ) is cyclic and regular.

Proof. Let F be the set of internal factors of the words of X and let M = ϕ A (A * ). Since X is finite, the ideal ϕ A (A * \ F ) contains any group G distinct from 1 in M and the result follows.

The following lemma is used in the proof of Theorem 1.

Lemma 4 Let X ⊂ A + be a code and let F be the set of internal factors of words in X. Let A = (Q, 1, 1) be a simple unambiguous automaton recognizing X * . Let G be a group contained in ϕ A (A * \ F ), let e be the neutral element of G and let R = Fix(e) be the set of fixpoints of e. For any g ∈ G, any word w ∈ ϕ -1 A (g) \ F and each r ∈ R, there is a unique interpretation α r of w such that there are paths r → sg (see Figure 6). This means that (r, sg) ∈ g contradicting the fact that g is a permutation on R. Proof of Theorem 1. Set A = (Q, 1, 1), and ϕ = ϕ A . Let G be a group contained in ϕ(A * \ F ) and let e be the neutral element of G. We first show that one may assume that G meets ϕ(X * ). We may suppose that G is not reduced to the empty relation since otherwise the group G is trivial and there is nothing to prove. Let w ∈ ϕ -1 (e) \ F . Since e is an idempotent which is not the empty relation, it has at least one fixpoint q. Since the automaton A is trim, there are words u, v ∈ A * such that 1 u → q and q v → 1. Then uwv is in X * . Since w / ∈ F , there exist t, z ∈ A * such that w = tz with ut, zv ∈ X * . Then q t → 1 and 1 z → q and thus zt ∈ X * . The set ϕ(z)Gϕ(t) is a group isomorphic to G by Proposition 2. It meets ϕ(X * ) since ϕ(z)eϕ(t) = ϕ(ztzt) ∈ ϕ(X * ). This shows that we may assume G meets ϕ(X * ).

Since G meets ϕ(X * ), the intersection G ∩ ϕ(X * ) is a subgroup by Proposition 1. This implies that e ∈ ϕ(X * ). Let w ∈ ϕ -1 (e) \ F . Thus w ∈ X * . Let R = Fix(e). Since e ∈ ϕ(X * ), we have 1 ∈ R. By Lemma 4, the word w has a set I of independent interpretations α r for r ∈ R such that r sα r → 1 and 1 pα r → r are simple or null paths. Set s r = s αr , f r = f αr , x r = c(f r ) and p r = p αr (see Figure 7). The map r → s r is injective since the interpretations are disjoint. This implies that R is finite and thus that G is finite.

Set R = {1, 2, . . . , n}. We may suppose that s i is a proper prefix of s i+1 for 1 ≤ i < n. We are going to prove that all elements of G are powers of the permutation α = (1 2 • • • n). This implies our conclusion since a subgroup of a cyclic and regular group is also cyclic and regular.

Denote by γ = (v 1 , v 2 , . . . , v ℓ ) the supremum of the interpretations α i of w. Since

s 1 = p 1 = 1, we have v 1 = v ℓ = 1. For 1 ≤ i ≤ n, set w = s i x i p i with x i = c(f i ).
We have

s i = v 1 • • • v i , x i = v i+1 • • • v j and p i = v j+1 • • • v ℓ (4)
with 1 ≤ i ≤ j < ℓ. Then, by Lemma 2, γ is n-periodic. Since w ∈ X * and x i ∈ X * , Equation (3) implies ji ≡ ℓ -2 ≡ 0 mod n.

(

) 5
Consider an element g ∈ G and a word z ∈ ϕ -1 (g). Then ϕ(wzw) = g. Since g ∈ G, by Lemma 4 the word wzw has a set J of n independent interpretations β i such that i s β i → 1 and 1

p β i → ig are simple or null paths. The path i w → i z → ig w → ig decomposes as i si → 1 xi → 1 pi → i z → ig sig → 1 xig → 1 pig → ig.
Thus the sequence (s i , x i p i zs ig x ig , p ig ) is an interpretation of wzw. Since the paths i si → 1 and 1 pig → are simple or null, this implies by uniqueness of β i that s βi = s i , c(f βi ) = x i p i zs ig x ig and p βi = p ig for 1 ≤ i ≤ n (see Figure 8). In particular, we have for each i ∈ R, p i zs ig ∈ X * .

The supremum of the interpretations β i is of the form

δ = (v 1 , v 2 , . . . , v ℓ-1 , u 1 , u 2 , . . . , u m , v 2 , . . . , v ℓ )
for some m > 0 and some nonempty words u 1 , . . . , u m such that z = u 1 • • • u m . Indeed, the first ℓ -1 terms of γ and δ coincide and the term of index ℓ of δ is u 1 instead of v ℓ which is empty. Similarly, the last ℓ -1 terms of γ and δ coincide and the term of index m of δ is u m instead of v 1 which is empty.

We then have for 1 ≤ i ≤ n, by Equation ( 4),

p i zs ig = v j+1 • • • v ℓ-1 u 1 • • • u m v 2 • • • v ig .
Thus, since c(f βi ) = x i p i zs ig x ig , we obtain, with the functions λ, µ, ν defined in (2),

µ(β i , J) = µ(α i , I) + ν(α i , I) + m + λ(α ig , I) + µ(α ig , I). Since µ(α i , I) ≡ µ(α ig , I) ≡ 0 mod n, we obtain µ(β i , J) ≡ ℓ -j -1 + m + ig -1 mod n. Since δ is n-periodic, we have ℓ -j -1 + m + ig -1 ≡ 0 mod n.
Since ℓ ≡ 2 mod n and i ≡ j mod n by Equation ( 5), this implies that -i + m + ig ≡ 0 mod n. Thus ig ≡ im mod n. Since this holds for 1 ≤ i ≤ n, we conclude that g = α -m . This shows that G is included in the cyclic group generated by α and thus that G is cyclic and regular.

Note that the permutation α of the above proof is not necessarily in G. This is the difficulty: the group G is cyclic but it has no obvious generator (see Example 8).

Examples

We illustrate the results on a series of examples.

The next three examples give instances of cyclic groups in the syntactic monoid of X * for a finite code X ⊂ A + with empty kernel on the alphabet A = {a, b}. Note that when the code is finite, by Corollary 3, all groups are cyclic and we do not have to distinguish between groups contained in ϕ(F ) and groups contained in ϕ(A * \ F ).

Example 6 Let X = {aa, bb, baa, bba}. The set X is a code with empty kernel. A simple unambiguous automaton recognizing X * is shown in Figure 9. The word a contains the cycle (12) and the word b the cycle (13).

Example 7 Let X = {aa, aba, bab, bb}. The set X is an infix code. The minimal automaton A of X * is represented in Figure 10.

The transition monoid M of A contains groups which are cyclic of order 1, 2 or 3. For example, ab contains the cycle (134) while a contains the cycle (12). Let us note an interesting feature of this example. Let G be the cyclic group of order 2 formed by the images of aa and aaa in M . The set ϕ -1 (G) is a submonoid which is not cyclic. It is not even finitely generated. Indeed, Figure 11 shows that any word w in (a ∪ babb * aba) * fixes globally the set {1, 2} and thus is such that ϕ(a 2 wa 2 ) ∈ G. Example 8 Let X = {aaa, aab, abaa, abab, baba, babb, bba, bbb}. The set X is an infix code. The minimal automaton A of X * is represented in Figure 12. The transition monoid M = ϕ(A * ) of A contains cyclic groups of degree 1, 2, 3 and 4. For example the word a contains the cycle (123).

In turn, ba contains the permutation (16)(23). This example shows another interesting feature. Consider the group G containing ϕ(ba). The neutral element of G is e = ϕ(baba) and its set of fixpoints is {1, 2, 3, 6}. The group G is of degree 4. It is composed of the permutation (16)(23) and the identity. It is thus of order 2. The permutation α of the proof of Theorem 1 is (1362) (see Figure 13). It does not belong to G. Actually, M does not contain any cyclic group of order 4.

Let us mention an interesting case where the hypothesis of the above theorem are satisfied. Let G be a transitive permutation group on R = {1, 2, . . . , n} and let ϕ : A * → G be a surjective morphism. Let H be the subgroup of G which fixes 1. Let Z be the bifix code generating the submonoid ϕ -1 (H). Let X be the set of elements of Z which have no proper factor in Z. Proposition 3 The set X is a finite infix code. The groups in the syntactic monoid M of X * , not reduced to the neutral element of M , are cyclic of degree at most n.

Proof. The set X is clearly an infix code. To prove that X is finite, consider a word z of Z of length at least equal to n + 2. Since z has at least n + 1 nonempty proper suffixes, there exist two distinct nonempty proper suffixes u, v of z such that 1ϕ(u) = 1ϕ(v). We may suppose that u is shorter than v. Then v = wu with 1ϕ(w) = 1ϕ(v)ϕ(u) -1 = 1 and thus w ∈ Z + . This shows that z ∈ X. This implies that the words in X have length at most n + 1 and thus that X is finite. Let M be the syntactic monoid of X * and let A be the minimal automaton of X * . By definition, we have M = ϕ A (A * ).

Let G ′ be a group contained in M not reduced to the neutral element of M . Let e be the neutral element of G ′ . By Corollary 3, G ′ is cyclic and regular. The degree of G ′ is equal to the rank of e.

Since G ′ = 1, the set ϕ -1 (e) contains nonempty words. Since it is a submonoid, it contains words of arbitrary large length. In particular, ϕ -1 (e) contains words of length larger than the length of any word in X and thus words which are not factor of a word in X. Let w be a word in ϕ -1

A (e) which is not a factor of a word in X. For any fixpoint p of e, there is an interpretation α of w with respect to X such that p sα → 1 and 1 pα → p. The interpretations corresponding to distinct fixpoints are distinct (and even independent). Since X ⊂ Z, these interpretations of w are also interpretations with respect to Z.

The number of interpretations of w with respect to Z is at most equal to n. Indeed, for each interpretation α of w with respect to Z, there is a unique r = r(α) ∈ R such that rϕ(s α ) = 1. Since the map α → r(α) is injective, the number of interpretations α is at most n. Thus w cannot have more than n interpretations with respect to X. This implies that the number of fixpoints of e is at most n and the degree of G ′ is also at most n.

Example 9 Let G be the symmetric group on the set R = {1, 2, 3} and let A = {a, b}. Let ϕ : A * → G be the morphism defined by ϕ(a) = (12), ϕ(b) = (13). The bifix code Z is the infinite set represented on the left of Figure 14. The code X corresponding to the above construction is

Complements

We first show in the following example that Theorem 1 becomes false for groups which do not meet the ideal ϕ A * (A * \ F ) and that the transition monoid of a simple unambiguous automaton recognizing X * may contain any finite or infinite group.

Example 12 Let G be a transitive permutation group on a set R and let ϕ : A * → G be a surjective morphism. Let 1 be an element of R and let H be the subgroup of G formed by the permutations fixing 1. Let Z be the bifix code such that Z * = ϕ -1 (H). Let B = (R, 1, 1) be the deterministic automaton recognizing Z * with edges (p, a, pϕ(a)) for p ∈ R and a ∈ A. Let B = A ∪ b where b ∈ A * is a new letter. Then X = bZ * b is an infix code. Let A = (Q, i, i) be the automaton obtained from B adding a state i / ∈ R and the two edges (i, b, 1), (1, b, i). Then A is a simple unambiguous automaton recognizing X * . Moreover G is isomorphic to a group contained in the transition monoid of A. It is formed of the images in M A of the words in A * acting as a permutation group (identical to G) on the elements of R.

We now prove the following result concerning the groups which do not satisfy the hypothesis of Theorem 1. We denote by M A the transition monoid of an automaton A.

Proposition 4 Let X ⊂ A + be a code with empty kernel and let F be the set of internal factors of the words of X. Let A = (Q, I, T ) be a trim unambiguous automaton recognizing X. Any group

H in M A * such that ϕ -1 A * (H) ⊂ F is isomorphic to a group in M A .
Note that this statement is false if the kernel of X is nonempty, as shown in the following example.

Example 13 Let X = a 2 ∪ ba * b and let A be the automaton represented on Figure 16 is a cyclic group of order 2 such that ϕ -1 A * (G) ⊂ F . We will use the following technical lemma.

Lemma 5 Let X be a code with empty kernel and let F be the set of internal factors of the words of X. Let A be a trim unambiguous automaton recognizing X. Let w be a nonempty word such that w * ⊆ F . Then: Proof 1. No power of w can have a factor in X. Indeed, if w n has a factor x ∈ X, then x ∈ F and thus belongs to the kernel of X. This proves the first assertion. 2. A path labeled by w can pass at most once by ω since otherwise it would have a factor in X. Note that if a word w satisfies the hypotheses of Lemma 5, they are also satisfied by any power w n with n ≥ 1 of w. We prove a second technical lemma.

1. w * ∩ A * XA * = ∅,
Lemma 6 Let X ⊂ A + be a code with empty kernel and let F be the set of internal factors of the words of X. Let A = (Q, I, T ) be a trim unambiguous automaton recognizing X. For a nonempty word w such that w * ⊂ F , there is an idempotent in ϕ A (w + ) if and only if there is one in ϕ A * (w + ).

Proof.

1. Suppose first that ϕ A (w + ) contains an idempotent. Changing w into some of its powers, we may assume that e = ϕ A (w) is an idempotent of M A . Set f = ϕ A * (w). Let us show that f 2 = f 3 , which implies that f 2 is idempotent. Suppose indeed that we have a path p w 2 → q in A * . If this path does not pass by ω, then it is a path in A and thus we have also p w 3 → q. Otherwise, since w 2 does not have a factor in X by Lemma 5, it can have only one occurrence of ω. We may suppose that this occurrence is in the first half of the path. The other case is symmetrical. Thus, suppose that we have w = uv with p u → ω and ω vw → q. Then, since the path ω vw → q does not pass by ω except at its origin, there is a path i vw → q in A for some i ∈ I. Since e = ϕ A (w) is idempotent, we also have a path i vw 2 → q in A and consequently a path ω vw 2 → q in A * . Finally, there is a path p w 3 → q in A * . This shows that f 2 ⊂ f 3 .

To show the converse inclusion, consider a path p w 3 → q in A * . If this path does not pass by ω, then it is a path in A and thus we have also a path p w 2 → q in A and thus in A * . Otherwise, suppose first that there is a factorization w = uv such that p u → ω vw 2 → q. Since ω does not have a second occurence on this path by Lemma 5, the path ω vw 2 → q does not pass by ω except at its origin. Thus, there is a path i vw 2 → q in A for some i ∈ I. Since e = ϕ A (w) is idempotent, there there is also a path i vw → q in A and thus a path ω vw → q in A * . Thus there is also a path p

u → ω vw → q in A * which is a path p w 2
→ q. The case where there is a path p

w 2 u → ω v → q in A * is similar. Finally, there cannot exist a path p wu → ω vw → q in A * with w = uv. Indeed, since e is idempotent, we have also paths p w 2 → r u → ω v → s w → q and p w → r u → ω v → s w 2
→ q for some r, s ∈ Q. By unambiguity, we obtain r = s and thus the existence of a path r u → ω v → r, which is impossible. This shows that f 3 ⊂ f 2 .

2. Conversely, suppose that f = ϕ A * (w) is idempotent. Let e = ϕ A (w). We show that e 2 = e 3 , which implies that e 2 is idempotent. Consider first a path p → q. This shows that e 2 ⊂ e 3 . The converse inclusion is proved in the same way by reversing the implications.

w 2 → q in A. Let u, v ∈ A * and s ∈ Q be such that i u → p w → s w → q v → t with i ∈ I and t ∈ T . By definition of A * , we also have a path ω u → p w → s w → q v → ω. Since f = ϕ A * (w) is idempotent with (p, q) ∈ f , by
Note that Lemma 6 is obvious when the code X is recognizable and the automaton A is finite. Indeed, in this case, the monoids M A and M A * are finite and in a finite monoid, any element has a power which is idempotent. The following examples illustrate the proof of Lemma 6.

Example 14 Let X = ab ∪ (cb) + cd which is a code with empty kernel on the alphabet A = {a, b, c, d}. A trim deterministic automaton A recognizing X and the corresponding automaton A * are shown on Figure 17.

It is easy to verify that e = ϕ A (bc) is idempotent while f = ϕ A * (bc) satisfies f 2 = f 3 (but f is not idempotent) illustrating point 1 in the proof of Lemma 6.

Example 15 Let X = ab ∪ abcd ∪ (cb) + cd which is a code with empty kernel on the alphabet A = {a, b, c, d}. A trim unambiguous automaton A recognizing X and the corresponding automaton A * are shown on Figure 18. It is easy to verify that f = ϕ A * (bc) is idempotent while e = ϕ A (bc) satisfies e 2 = e 3 (but e is not idempotent), thus illustrating point 2 in the proof of Lemma 6.

Proof of Proposition 4. Since the monoids M A and M A * both contain the group reduced to the identity, we may discard the case of groups reduced to the identity of M A or M A * , and thus of groups G such that ϕ

-1 A * (G) = 1 or ϕ -1 A (G) = 1. Note that if ϕ -1 A (G) = 1, then ϕ -1 A (g) = 1 for any g ∈ G.
The same holds for ϕ A * . We may also discard the case of the group reduced to the empty relation in M A .

Let f be an idempotent in M A * such that ϕ -1 A * (f ) ⊂ F . We may assume that X is not empty and thus that f = 0. By the above discussion, we may assume ϕ nonempty word in ϕ -1 A * (f ). Since ϕ A * (w + ) = {f }, by Lemma 6 there is an integer n ≥ 1 such that ϕ A (w n ) is an idempotent e of M A . By assertion 4 of Lemma 5 applied to w n , the set of fixpoints of e and f are equal. Thus, in particular e is not the empty relation. We are going to prove that the maximal groups containing e and f respectively are isomorphic. This will prove the statement since any group in M A * is contained in a maximal group.

Set R = Fix(e) = Fix(f ). Let G be the maximal group in M A containing e and H be the maximal group in M A * containing f . We are going to prove that G and H are equal as permutation groups on R. Let h be an element of H and let u be a nonempty word in ϕ -1 A * (h). Let v be a nonempty word in ϕ -1 A * (h -1 ). Then ϕ A * (uv) = f . Let r, s ∈ R be such that r u → s in A * and thus also s v → r. By Lemma 5 applied to uv, the path r u → s cannot pass by ω since otherwise the path r u → s v → r would pass by ω. Thus, we also have a path r u → s in A. This shows that G contains the permutation defined by h on R. Conversely, let g be an element of G and u, v be a nonempty words such that ϕ A (u) = g, ϕ A (v) = g -1 . Let r, s ∈ R be such that there is a path r u → s in A. Since there is also a path s v → r in A, all states on the path r u → s belong to the trim part of the automaton B used to build A * (see the definition of A * in Section 2.2). Thus they are states of A * . This shows that we also have a path r u → s in A * and proves that H contains the permutation g. Thus G and H are equal as permutation groups on R.

Observe that it is not true in general that any idempotent e = 0, 1 in M A is obtained as in the proof above from an idempotent f ∈ M A * such that ϕ -1 A * (f ) ⊂ F , as shown in the following example.

Example 16 Let A and A * be the automata given in Figure 19. The automaton A is a trim de- We conclude with a consequence of the main result (Theorem 1) and of Proposition 4 concerning a closure property of a variety of finite monoids. Recall (see [START_REF] Eilenberg | With two chapters ("Depth decomposition theorem[END_REF] for an introduction) that a variety of finite monoids is a class V of finite monoids which is closed under (i) morphism: if ϕ : M → N is a morphism of monoids and M ∈ V, then N ∈ V, (ii) submonoid: if M ∈ V, any submonoid of M is in V, (iii) finite direct product: if M, N ∈ V, then M × N ∈ V.

A variety of finite monoids is also called a pseudovariety of monoids, the name of a variety (in the sense of Birkhoff) being used when condition (iii) is replaced by the closure under arbitrary (possibly infinite) direct product. For simplicity, we use here the term of variety instead of pseudovariety.

The * -variety associated to a given variety V of finite monoids is, for each alphabet A, the family of recognizable sets S ⊂ A * such that the syntactic monoid of S belongs to the variety V. Such a class is closed under boolean operations and residual: if X ⊂ A * is in V then for any u ∈ A * , u -1 X = {v ∈ A * | uv ∈ X} and Xu -1 = {v ∈ A * | vu ∈ X} are in V.

For any variety G of finite groups, the class of finite monoids containing only groups in G is a variety (see [START_REF] Eilenberg | With two chapters ("Depth decomposition theorem[END_REF]). By a theorem of Schützenberger, the corresponding * -variety V is closed under product: if X, Y ∈ V, then XY ∈ V.

Let V be the variety of finite monoids containing only Abelian groups. Let V be the associated * -variety of sets. This variety has been studied by Schützenberger, who has described the * -variety V using another closure property (see [START_REF] Schützenberger | Sur les monoides finis dont les groupes sont commutatifs[END_REF] or [START_REF] Lallement | Semigroups and combinatorial applications[END_REF]).

Theorem 2 For any code X with empty kernel which belongs to V, the set X * is in V.

Proof. Let A be the minimal deterministic automaton of X. The transition monoid of A is the syntactic monoid of X and therefore is in the variety V. The automaton A * is a simple unambiguous automaton recognizing X * . We show that the transition monoid M of A * is in V. Since the syntactic monoid of X * is a quotient of M , this will prove that X * is in V. Let F be the set of internal factors of the words of X. Let G be a group contained in M . If G is contained in the ideal ϕ A * (A * \ F ), then G is cyclic by Theorem 1. Otherwise, by Proposition 4, G is isomorphic to a group contained in the transition monoid of A and thus G is Abelian.

Figure 3 :

 3 Figure 3: Two connected interpretations

Figure 4 :

 4 Figure 4: The 8 factorizations of w = ab and the 4 factorizations of a -1 w = b.

Figure 5 :

 5 Figure 5: A cyclic set of two interpretations

→ 1 f→ r and rg h → 1 .→ 1 xv→ rg and s ux → 1 v→

 1111 rg which are simple or null. Moreover, the setI = {α r | r ∈ R} is formed of independent interpretations.Proof. For each r ∈ R, there is a path r w → rg. Since A is trim, there exist f, h ∈ A * such that Since w / ∈ F , there exists an interpretation α r of w such that r rg are simple or null paths. This interpretation is clearly unique. The interpretations α r , for r ∈ R, are independent. Suppose indeed that for r, s ∈ R there are u, v ∈ A * and x ∈ X * such that w = uxv, u ∈ P (α r ) and ux ∈ P (α s ). Then we have the paths r u → sg, which imply the existence of a path r

Figure 6 :

 6 Figure 6: The interpretations α r and α s are independent.

Figure 7 :

 7 Figure 7: The interpretation α r .

Figure 8 :

 8 Figure 8: An interpretation of wzw.

Figure 9 :Figure 10 :

 910 Figure 9: A code with empty kernel defining cyclic groups of order 2.

Figure 11 :

 11 Figure 11: The action of A * on the 2-element subsets reachable from {1, 2}

Figure 12 :

 12 Figure12: An infix code with a group of degree 4 and order 2.

Figure 13 :

 13 Figure 13: The interpretations of baba.

Figure 14 :Figure 15 :

 1415 Figure 14: The infinite group code Z and the finite code X represented on the right of Figure 14. It is the code of Example 7. Example 10 The code X of Example 8 corresponds to the above construction with G being the symmetric group on the set {1, 2, 3, 4} and ϕ(a) = (123), ϕ(b) = (143). Example 11 Let us consider the morphism from {a, b} * to the symmetric group on {1, 2, 3, 4, 5} defined by ϕ(a) = (123), ϕ(b) = (145). Then X = {aaa, aaba, aabba, abaa, ababa, abbaa, baabb, babab, babb, bbaab, bbab, bbb}.The transitions of the minimal automaton A of X * are represented in Figure15. The monoid M has 14351 elements. It contains cyclic groups of degrees from 1 to 5 and orders 1, 2, 3, 5. The word ab contains the cycle (1 6 11 4 9) of length 5 and (ab) 2 has rank 5 (there is a second D-class of elements of degree 5 containing the image of a 2 b 2 ). The word a 2 ba 2 b 2 contains the permutation (1 12)(5 11) of degree 4 but there is no cyclic group of order 4 in M . The words a and b contains cycles of degree 3. The word a 4 ba 5 contains the identity on {1, 2} while the word a 2 bab 2 a 2 ba 4 contains the transposition (1 2).

Figure 16 :

 16 Figure 16: The automata A and A * .

2. a path p w →

 w q in the automaton A * can pass at most once by ω, 3. no path r w → r in the automaton A * can pass by ω, 4. F ix(ϕ A (w)) = F ix(ϕ A * (w)).

3 .

 3 Follows from 2 since, otherwise, the path r w → r w → r in A * passes twice by ω. 4. All fixpoints of ϕ A (w) are also fixpoints of ϕ A * (w) and, by assertion 3, ϕ A * (w) cannot have other fixpoints.

A and finally a path p w 3

 3 Lemma 3, there is a path p w → r w → q in A * with r ∈ Fix(f ). By unambiguity we have r = s.By Lemma 5 the path s w → s does not pass by ω. Thus we also have a path p

Figure 17 :

 17 Figure 17: The automata A and A * for X = ab ∪ (cb) + cd.

Figure 18 :

 18 Figure 18: The automata A and A * for X = ab ∪ abcd ∪ (cb) + cd.

Figure 19 :

 19 Figure 19: The automata A and A *