Jean Néraud
email: neraud.jean@gmail.com

Carla Selmi
email: carla.selmi@univ-rouen.fr

Embedding a θ-invariant code into a complete one

Keywords: antimorphism, anti-automorphism, automorphism, (anti-)automorphism, Bernoulli distribution, bifix, code, complete, context-free, defect, equation, finite, invariant, involutive, label, maximal, morphism, order, overlap, overlapping-free, prefix, regular, suffix, thin, tree, θ-invariant, θ-code, uniform, variable-length code

Let A be an arbitrary alphabet and let θ be an (anti-)automorphism of A * (by definition, such a correspondence is determinated by a permutation of the alphabet). This paper deals with sets which are invariant under θ (θ-invariant for short) that is, languages L satisfying θ(L) ⊆ L. We establish an extension of the famous defect theorem. With regard to the socalled notion of completeness, we provide a series of examples of finite complete θ-invariant codes. Moreover, we establish a formula which allows to embed any non-complete θ-invariant code into a complete one. As a consequence, in the family of the so-called thin θ-invariant codes, maximality and completeness are two equivalent notions.

Introduction

In the free monoid theory, during the last decade, research involving one-to-one morphic or antimorphic substitutions has played a particularly important part: this is due to the powerful applications of these objects, in particular in the framework of DNA-computing. In the case of automorphisms or anti-automorphisms -for short we write (anti-)automorphismsgiven an arbitrary alphabet, say A, any such mapping is completely determined by extending a unique permutation of A to A * , the free monoid that is generated by A.

In the special case of involutive (anti-)automorphisms, lots of successful investigations have been done for extending most of the now classical combinatorial properties on words. The topics of the so-called pseudo-palindromes [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF], that of θ-episturmian words [START_REF] Bucci | On θ-episturmian words[END_REF], and the one of pseudo-repetitions [START_REF] Deva Priya Darshini | Factors of words under an involution[END_REF][START_REF] Gawrychowski | Finding pseudo-repetitions[END_REF] have been particularly involved. The framework of some peculiar families of variable-length codes [START_REF] Kari | Dna codes and their properties[END_REF] and that of equations in words [START_REF] Czeizler | An extension of the Lyndon-Schützenberger result to pseudoperiodic words[END_REF][START_REF] Day | Equations enforcing repetitions under permutations[END_REF][START_REF] Kari | Watson-Crick conjugate and commutative words[END_REF][START_REF] Manea | Generalised Lyndon-Schützenberger equations[END_REF] have been concerned. Generalizations of the famous theorem of Fine and Wilf ( [START_REF] Fine | Uniqueness theorem for periodic functions[END_REF], [START_REF] Lothaire | Combinatorics on Words[END_REF]Proposition 1.3.5]) were also established [START_REF] Czeizler | On a special class of primitive words[END_REF][START_REF] Manea | Fine and Wilf's theorem and pseudo-repetitions[END_REF].

Equations in words are also the starting point of the study in the present paper, which consists in some full version of [START_REF] Néraud | Invariance: a theoretical approach for coding sets of words modulo literal (anti)morphisms[END_REF]. Let A be an arbitrary alphabet and let θ be an (anti-)automorphism of A * ; we adopt the point of view from [START_REF] Lothaire | Combinatorics on Words[END_REF]Ch. 9], by considering a finite collection of unknown words, say Z. We assume that a (minimum) positive integer k (i.e. the so-called order of θ) exists such that θ k = id A * . This condition is particularly satisfied by every (anti-)automorphism whenever A is finite. In view of making the present forward more easily readable, in the first instance let us take θ as an involutive (anti-)automorphism (that is, θ 2 = id A * ). We assign that the words in Z and their images by θ to satisfy a given equation, and we ask for the computation of a finite set of words, say Y , such that all the words of Z can be expressed as a concatenation of words in Y . Actually, such a question appears more complex than in the classical configuration, where θ does not interfer: in this classical case, according to the famous defect theorem [18, Theorem 1.2.5], it is well known that at most |Z| -1 words allow to compute the words in Z. At the contrary, due to the interference of (anti-)automorphisms, in [START_REF] Kari | Watson-Crick conjugate and commutative words[END_REF], examples where |Y | = |Z| are provided by the authors.

Along the way, for solving our problem, applying the defect theorem to the set X = Z ∪ θ(Z) might appear natural. Such a methodology garantees the existence of a set Y , with |Y | ≤ |X| -1 and whose elements allow by concatenation to rebuild all the words in X. It is also well known that Y can be chosen in such a way that only trivial equations may hold among its elements: with the terminology of [START_REF] Berstel | Codes and Automata[END_REF][START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF], Y is a code, or equivalently Y * , the submonoid that it generates, is free. Unfortunately, since both the words in Z and θ(Z) are expressed as concatenations of words in Y , among the words of Y ∪ θ(Y ) non-trivial equations can still hold. In other words, by applying that methodology, the initial problem would be transferred among the words in Y ∪ θ(Y ).

An alternative methodology will consist in asking for codes Y which are invariant under θ (θ-invariant for short) that is, satisfying θ(Y ) = Y . Returning to the general case, where θ is an arbitrary (anti-)automorphism, this is equivalent to say that the union of the sets θ i (Y ), for all i ∈ Z, is θ-invariant. By the way, it is straightforward to show that the intersection of an arbitrary family of free θ-invariant submonoids is itself a free θ-invariant submonoid.

In the present paper we prove the following result: Theorem 1. Let θ be an (anti-)automorphism of A * and let X be a finite θ-invariant set. If X it is not a code, then the smallest θ-invariant free submonoid of A * containing X is generated by a θ-invariant code Y , which furthermore satisfies |Y | ≤ |X| -1.

For illustrating this result in terms of equation, we refer to [START_REF] Czeizler | An extension of the Lyndon-Schützenberger result to pseudoperiodic words[END_REF][START_REF] Manea | Generalised Lyndon-Schützenberger equations[END_REF], where the authors considered generalizations of the famous three unknown variables equation of Lyndon-Shützenberger [18, § 9.2]. They proved that, an involutive (anti-)automorphism θ being fixed, given such an equation with sufficiently long members, a word t exists such that any 3-uple of "solutions" can be expressed as a concatenation of words in {t} ∪ {θ(t)}. With the notation of Theorem 1, the elements of the θ-invariant set X are x, y, z, θ(x), θ(y), θ(z) and those of Y are t and θ(t): we verify that, in every case Y is a θ-invariant code, furthermore we have

|Y | ≤ |X| -1.
With regard to the theory of codes, completeness is one of the most challenging notions: a subset X of the free monoid A * is complete if any word is a factor of some word in X * . Maximality is another important notion: a code is maximal if it cannot be strictly included in some other code of A * . Actually, according to Zorn's Lemma, any code is included in a maximal one moreover, a famous result due to Schützenberger states that, for the family of the so-called thin codes (which contains the regular codes), maximality and completeness are two equivalent notions [START_REF] Berstel | Codes and Automata[END_REF]Theorem 2.5.16]. From this point of view, in the second part of our study we are interested in complete θ-invariant codes. It is natural to prealably examine the case of finite codes. Clearly, the well-known complete uniform codes that is, the codes A n (with n ≥ 1), are invariant under every (anti-)automorphism. Beside that, non-trivial 2 finite complete θ-invariant codes exist: for instance, take for A the binary alphabet {a, b}, choose for θ the anti-automorphism that swaps the letters a and b, and consider the complete code which was introduced in [START_REF] Césari | Sur un algorithme donnant les codes bipréfixes finis[END_REF]:

X = {a 3 , ab, a 2 ba, a 2 b 2 , ba 2 , baba, bab 2 , b 2 a, b 3 }.
It is straightforward to verify that X is θ-invariant. In our paper, we provide some other examples: each of the classes of bifix codes, prefix codes, and non-prefix non-suffix codes is concerned.

Despite that, the question of describing a general structure for finite complete θ-invariant codes remains largely open: this is not surprizing since, with the exception of certain special families (e.g. [START_REF] Felice | Construction of a family of finite maximal codes[END_REF][START_REF] De Felice | Some results on finite maximal codes[END_REF][START_REF] Restivo | Completing codes[END_REF]), no general structure that could embrace finite complete codes is described in the literature.

Another issue could consist in developing methods for embedding a code into a complete one. However, in [START_REF] Restivo | On codes having no finite completion[END_REF], the author presents a class of codes that cannot be embedded into any finite complete one. With regard to θ-invariance, as far as we know, the question of embedding finite codes into complete ones remains open.

Actually, in [START_REF] Restivo | On codes having no finite completion[END_REF], the question whether any finite code can be embedded into a regular one was implicitely asked: a positive answer was brought in [START_REF] Ehrenfeucht | Each regular code is included in a regular maximal one[END_REF], where the authors provided a now classical formula for embedding any regular code into a complete one. In the present paper, we put a corresponding problem in the framework of θ-invariant codes. Actually, by establishing the following result, we bring a positive answer: Theorem 2. Any non-complete θ-invariant code X ⊆ A * , can be embedded into a complete one. Moreover, if A is finite and X regular, then X can be embedded into a regular complete θ-invariant code.

As a consequence, we obtain the following result: it states that, in the framework of θinvariant codes, a property similar to a famous one due to Schützenberger [1, Theorem 2.5.16] holds: Theorem 3. Given a thin θ-invariant code X ⊆ A * , the five following conditions are equivalent:

(i) X is complete. (ii) X is a maximal code.
(iii) X is maximal in the family of the θ-invariant codes. (iv) A positive Bernoulli distribution π exists such that π(X) = 1. (v) For any positive Bernoulli distribution π, we have π(X) = 1.

We now describe the contents of our paper. Section 2 contains the preliminaries: the terminology of the free monoid is settled, and we recall some classical notions and results concerning the codes. The preceding Theorem 1 is established in Section 3, where an original example of equation is studied. In Section 4, we present several examples of finite complete θ-invariant codes. The problem of embedding a finite θ-invariant code into a complete one is also discussed: this ensures a transition to the question of embedding a regular θ-invariant code into a complete one. This last question is studied in Section 5, where the preceding Theorem 2 and Theorem 3 are established.

Preliminaries

Words and free monoid

We adopt the notation of the free monoid theory. In the whole paper, we consider an alphabet A, and we denote by A * the free monoid that it generates. Given a word w ∈ A * , we denote by |w| its length, the empty word, which we denote by ε, being the word with length 0. Given a subset X of A * , we denote by X * the submonoid of A * that is generated by X, moreover we set X + = X * \ {ε}.

Let x ∈ A * and w ∈ A + . We say that x is a prefix (suffix) of w if a word u exists such that w = xu (w = ux). Similarly, x is a factor of w if two words u, v exist such that w = uxv. Given a non-empty set X ⊆ A * , we denote by P (X) (S(X), F (X)) the set of the words that are prefix (suffix, factor) of some word in X. Clearly, we have X ⊆ P (X) ⊆ F (X) (X ⊆ S(X) ⊆ F (X)). Given a pair of non-empty words w, w , we say that it overlaps if words u, v exist such that uw = wv or w u = vw, with 1 ≤ |u| ≤ |w| -1 and 1 ≤ |v| ≤ |w | -1; otherwise, the pair is overlapping-free (in such a case, if w = w , we simply say that w is overlapping-free).

Variable length codes

It is assumed that the reader has a fundamental understanding with the main concepts of the theory of variable-length codes: we only recall some of the main definitions and we suggest, if necessary, that he (she) report to [START_REF] Berstel | Codes and Automata[END_REF]. A subset X of A * is a variable-length code (a code for short) if any equation among the words of X is trivial that is, for any pair of sequences of words in X, say (x i ) 1≤i≤n , (y j ) 1≤j≤p , the equation

x 1 • • • x n = y 1 • • • y p implies n = p and x i = y i , for each integer i ∈ [1, n]. By definition X * is a free submonoid of A * .
In the present paper the so-called prefix, suffix and bifix codes play an noticeable part: a A positive Bernoulli distribution is a morphism π from the free monoid A * onto the multiplicative monoid [0, 1], such that we have π(a) > 0 for every a ∈ A, and such that a∈A π(a) = 1. The uniform distribution corresponds to π(a) = 1/|A|, for every letter a. For any subset X of A * , we set π(X) = x∈X π(x). Clearly, the last sum may be finite or not, however if X is a thin subset we have π(X) < ∞ [1, Proposition 2.5.12]; moreover for every code X ⊆ A * , we have π(X) ≤ 1. From this point of view, the following result was established by Shützenberger (e.g. [1, Theorem 2.5.16]): Theorem 2.1. Given a thin code X ⊆ A * , the four following conditions are equivalent:

code X ⊆ A * is prefix (suffix) if X ∩ XA + = ∅ (X ∩ A + X = ∅). A code is bifix if it is both prefix and suffix. A code X ⊆ A * is maximal if it is not strictly included in some other code of A * . Given a set X ⊆ A * , it is complete if A * = F (X * ); X is thin if A * = F (X).
(i) X is complete. (ii) X is a maximal code. (iii) A positive Bernoulli distribution π exists such that π(X) = 1.
(iv) For any positive Bernoulli distribution π, we have π(X) = 1.

(Anti-)automorphisms

In the whole paper, we fix an alphabet A and a mapping θ onto A * which is either an automorphism or an anti-automorphism: it is an anti-automorphism if it is one-to-one, with θ(ε) = ε and θ(xy) = θ(y)θ(x), for any pair of words x, y. For short in any case we write that θ is an (anti-)automorphism.

We say that the (anti-)automorphism θ is of finite order if some positive integer k exist such that θ k = id A * , the smallest one being the so-called order of θ (trivially id A * is of order 1). It is well known that such a condition is satisfied whenever A is a finite set; in particular, over a two letter alphabet, any non-trivial (anti-)automorphism is of order 2 that is, it is involutive.

In the whole paper, we are interested in the family of sets X ⊆ A * that are invariant under θ (θ-invariant for short) that is, which satisfy θ(X) ⊆ X; the mapping θ being one-to-one, this is equivalent to θ(X) = X.

Example 1. Let A = {a, b, c, d}. Consider the (unique) anti-automorphism θ that is defined by θ(a) = a, θ(b) = b, θ(c) = d, θ(d) = c.
It is straightforward to verify that the mapping θ is involutive, moreover the sets {cd} and {abcd, cdba} are θ-invariant.

Remark 1. In the spirit of the families of codes that were introduced in [START_REF] Kari | Dna codes and their properties[END_REF], given an (anti-)automorphism θ, define a θ-code as a set X such that i∈Z θ i (X) is a code. Clearly, with this definition any θ-code is a code; the converse is false, as attested below by Example 2.

Actually, any θ-code that is a maximal code, is necessarily θ-invariant. Indeed, assuming X not θ-invariant, we have X X ∪θ(X), thus X is strictly included in the code i∈Z θ i (X).

A similar argument proves that if X is maximal as a θ-code, then it is θ-invariant (indeed,

i∈Z θ i (X) itself is a θ-code).
Taking account of the fundamental importance of the concept of maximality in the theory of codes, such properties reinforces the relevance of the notion of θ-invariant code.

Example 2. Let A = {a, b} and θ be the so-called mirror antimorphism:

θ(a) = a, θ(b) = b.
Take for X the finite (prefix) code {a, ba}. We have X ∪ θ(X) = {a, ab, ba}, which is not a code (ab • a = a • ba).

A defect effect for invariant sets

We start with some considerations about θ-invariant submonoids of A * . Clearly the intersection of a non-empty family of θ-invariant free submonoids of A * is itself a θ-invariant free submonoid. Given a submonoid M of A * , recall that its minimal generating set is (M \ {ε}) \ (M \ {ε}) 2 . The following property holds: Proposition 3.1. Given an alphabet A and given an (anti-)automorphism θ of A * , let M be a submonoid of A * and let S ⊆ A * such that M = S * . Then the two following properties hold:

(i) If S is θ-invariant then the same holds for M . (ii) If S is the minimal generating set of M and if M is θ-invariant then S is θ-invariant.
Proof. (i) Assume that the set S is θ-invariant, and let w ∈ M . Since M = S * , a finite sequence of words in S, namely

(s i ) 1≤i≤n , exists such that w = s 1 • • • s n . Since θ is an (anti- )automorphism, in every case θ(w) is some concatenation of the words θ(s i ) (1 ≤ i ≤ n), therefore we have θ(w) ∈ S * = M . Consequently M is θ-invariant. (ii) Assume that M is θ-invariant and let s ∈ S. It follows from S ⊆ M that we have θ(s) ∈ θ(M ) = M therefore, a sequence of words in S, namely (s i ) 1≤i≤n , exists such that θ(s) = s 1 • • • s n . Since θ is an (anti-)automorphism, s is in fact some concatenation of the words θ -1 (s 1 ), • • • , θ -1 (s n ) ∈ M . Moreover, for each integer i ∈ [1, n], we have θ -1 (s i ) = s 1 i • • • s ni i , with s j i ∈ S (1 ≤ j ≤ n i ).
It follows from the definition of S that we have n = 1 and s = s

1 1 = θ -1 (s 1 ), thus θ(s) = s 1 ∈ S. As a consequence, S itself is θ-invariant.
Informally, the famous defect theorem says that if some words in a set X satisfy a nontrivial equation, then these words can be written upon an alphabet of smaller size. In this section, we will examine whether a corresponding result may be stated in the framework of θ-invariant sets. Theorem 3.2. Given an alphabet A and given an (anti-)automorphism θ of A * , let X ⊆ A * be a θ-invariant set. Let Y be the minimal generating set of the smallest θ-invariant free submonoid of A * that contains X. If X is not a code, then we have

|Y | ≤ |X| -1.
With the notation of Theorem 3.2, since Y is a code, each word x ∈ X has a unique factorization upon the words of Y , namely

x = y 1 • • • y n , with y i ∈ Y (1 ≤ i ≤ n).
In a classical way, we say that y 1 (y n ) is the initial (terminal) factor of x (with respect to such a factorization). From this point of view, before to prove Theorem 3.2, we need to establish the following statement: Lemma 3.3. With the preceding notation, each word in Y is the initial (terminal) factor of some word in X.

Proof. By contradiction, assume that a word y ∈ Y that is never initial of any word in X exists. Set Z 0 = (Y \ {y}){y} * and Z i = θ i (Z 0 ), for each integer i ∈ Z. In a classical way (see e.g. [18, p. 7]), since Y is a code, Z 0 itself is a code. For each integer i ∈ Z, since θ i is itself an (anti-)automorphism, Z i is a code that is, Z * i is a free submonoid of A * . Consequently, the intersection, say M , of the family

(Z * i ) i∈Z is itself a free submonoid of A * . Let w ∈ M . For each integer i ∈ Z, we have w ∈ Z * i , thus θ(w) ∈ θ(Z * i ) ⊆ (θ(Z i )) * = (θ i+1 (Z 0 )) * = Z * i+1 . Consequently we have θ(w) ∈ i∈Z Z * i+1 = i∈Z Z * i = M , whence we have θ(M ) ⊆ M therefore, since θ is onto, we obtain θ(M ) = M .
Let x be an arbitrary word in X. Since X ⊆ Y * , and according to the definition of y,

we have x = (z 1 y k1 )(z 2 y k2 ) • • • (z n y kn ), with n ≥ 1, z 1 , • • • z n ∈ Y \ {y} and k 1 , • • • k n ≥ 0. Consequently x belongs to Z * 0 , therefore we have X ⊆ Z * 0 . Since X is θ-invariant, this implies X = θ i (X) ⊆ θ i (Z * 0 ) ⊆ Z * i , for each i ∈ Z, thus X ⊆ M .
But the word y belongs to Y * and does not belong to Z * 0 thus, it doesn't belong to M . This implies X ⊆ M Y * : a contradiction with the minimality of Y * . Clearly, similar arguments may be applied to words y ∈ Y that are never terminal of any word in X: this completes the proof.

Proof of Theorem 3.2. Let α be the mapping from X onto Y which, with every word x ∈ X, associates the initial factor of x in its (unique) factorization over Y * . According to Lemma 3.3, α is onto. We will prove that it is not one-to-one. Classically, since X is not a code, a non-trivial equation may be written among its words, say:

x 1 • • • x n = x 1 • • • x p , with x i , x j ∈ X x 1 = x 1 (1 ≤ i ≤ n, 1 ≤ j ≤ p). Since Y is a code, a unique sequence of words in Y , namely y 1 , • • • , y m (m ≥ 1) exists such that: x 1 • • • x n = x 1 • • • x p = y 1 • • • y m . This implies y 1 = α(x 1 ) = α(x 1 ) and completes the proof.
In what follows we discuss some interpretation of Theorem 3.2 with regard to equations in words. For this purpose, we assume that A is finite, θ being of order k, and we consider a finite set of words, say Z. Let X be the union of the sets θ i (Z), for i ∈ [0, k -1], and assume that a non-trivial equation holds among the words of X, namely

x 1 • • • x m = y 1 • • • y p . By construction X is θ-invariant therefore, according to Theorem 3.2, a θ-invariant code Y exists such that X ⊆ Y * , with |Y | ≤ |X| -1.
This means that each of the words in X can be expressed by making use of at most |X| -1 words of type θ i (u), with u ∈ Y and 0 ≤ i ≤ k -1. It will be easily verified that the examples from [START_REF] Czeizler | An extension of the Lyndon-Schützenberger result to pseudoperiodic words[END_REF][START_REF] Kari | Watson-Crick conjugate and commutative words[END_REF][START_REF] Manea | Generalised Lyndon-Schützenberger equations[END_REF] corroborate this fact; moreover, below we mention an original one: Example 3. Let θ be an anti-automorphism of order 3. Consider two different words x, y, with |x| > |y| > 0, satisfying the equation: xθ(y) = θ 2 (y)θ(x). With this condition, a pair of words u, v exists such that x = uv, θ(x) = vθ(y), θ 2 (y) = u, thus y = θ(u). It follows

from x = uv that vθ(y) = θ(x) = θ(v)θ(u), thus v = θ(v) and θ(y) = θ(u). This implies y = u = θ(u) = θ 2 (u) and v = θ(v) = θ 2 (v)
. Moreover, we have θ(x) = vu, θ 2 (x) = uv: we obtain x = θ 2 (x) thus, x = θ(x) = θ 2 (x); hence we have uv = vu. Consequently, a nonempty word t and integers i, j exist such that u = t i , v = t j . With the preceding notation, we have

Z = {x, y}, X = Z ∪ θ(Z) ∪ θ 2 (Z) = {x, y}, Y = {t}. We verify that |Y | ≤ |X| -1.

Finite complete θ-invariant codes

In this section we are interested in finite complete θ-invariant codes over an alphabet A. Given an arbitrary letter a ∈ A, since for every non-negative integer n, we have a n ∈ F (X * ), necessarily a (unique) positive integer p exists such that a p ∈ X; therefore, A is necessarily finite. Several examples of finite complete θ-invariant codes will be presented. We start with prefix codes, which certainly constitute the best-known class of them.

Finite complete prefix θ-invariant codes

Actually finite complete prefix codes play a peculiar part in the framework of codes. A famous result due to Schützenberger [START_REF] Schützenberger | On a question concerning certain free submonoids[END_REF] (cf. also [START_REF] Bruyère | Automata and codes with a bounded deciphering delay[END_REF]) states that any finite complete code with a finite deciphering delay (e.g. [START_REF] Berstel | Codes and Automata[END_REF]Ch. 5]) is necessarily a prefix code. In particular, over A * only one finite complete circular code (or, equivalently, finite complete uniformly synchronized code) can exist, namely the alphabet A itself (cf. [1, Ch. 7, Ch. 10], [START_REF] Lassez | Circular codes and synchronization[END_REF]).

It is well-known that each prefix set, say X, can be represented by a tree, say T (X), of arity |A|: in this representation, each node (i.e. vertice) is a prefix of some word in X (i.e. an element of P (X)), the root being ε, the empty word. Moreover, given two nodes u, v and a letter a ∈ A, an edge with label a exists from u to v in T (X) if, and only if, we have v = ua: we denote such a labeled edge by (u, a, v) and we say that v is a successor of u. In that representation, complete prefix codes correspond to complete trees, in the sense where each interior node has exactly |A| successors.

We start with the case where θ is an automorphism of A * . Given a prefix set X ⊆ A * , we say that the corresponding tree T (X) is invariant under θ whenever (u, a, v) is an edge of T (X) if, and only if, (θ(u), θ(a), θ(v)) is an edge of T (X). With this notion, a characterization of θ-invariant prefix codes may be stated: Claim 1. Let A be a finite alphabet, let θ be an automorphism of A * and let X be a prefix code. Then X is θ-invariant if, and only if, the tree T (X) itself is invariant under θ.

Proof. Assume that X is θ-invariant, and let (u, a, ua) an arbitrary edge in T (X). By construction a word s ∈ S(X) exists such that uas ∈ X. Since X is a θ-invariant set, this implies θ(u)θ(as) = θ(ua)θ(s) ∈ X, thus θ(u) and θ(ua) ∈ P (X). Consequently, (θ(u), θ(a), θ(u)θ(a)) is an edge of T (X), therefore T (X) is invariant under θ.

Conversely, assume that T (X) is invariant under θ.

Let w = w 1 • • • w n ∈ X, with w i ∈ A (1 ≤ i ≤ n).
By construction, the following sequence of edges exists in T (X) (for i = 0, we set

w 1 • • • w i = ε): (w 1 • • • w i , w i+1 , w 1 • • • w i+1 ) (0 ≤ i ≤ n -1),
moreover the node w = w 1 • • • w n has no successor. Since T (X) is invariant under θ, a corresponding sequence of edges exists in T (X), namely:

(θ(w 1 ) • • • θ(w i ), θ(w i+1 ), θ(w 1 ) • • • θ(w i+1 )) (0 ≤ i ≤ n -1).
Since the node w 1 • • • w n has no successor, the same holds for the corresponding node θ(w Given an arbitrary integer n ≥ 3, consider the following set:

) = θ(w 1 • • • w n ): this implies θ(w) ∈ X.
X = 1≤i≤n-1 {a i b, b i a} ∪ {a n , b n }.
By construction, X is a prefix code. Moreover, X is complete: this can be directly verified by examining T (X) (an alternative method consists in applying Theorem 2.1 (iii), with π the uniform Bernoulli distribution). It is also straightforward to verify that X is θ-invariant.

Note that X is not bifix: indeed, for each integer i ∈ [2, n -1], the word ab ∈ X is a suffix of a i b ∈ X. Figure 1 illustrates the corresponding tree T (X) for n = 4.

In the case where θ is an anti-automorphism, the following property is noticeable: Claim 2. Let θ be an anti-automorphism onto A * and let X ⊆ A * be a finite θ-invariant code. If X is prefix, then it is necessarily bifix.

Proof. By contradiction, assume X not bifix, thus not suffix: words p A * , s ∈ A + exist such that s, ps ∈ X. Since X is θ-invariant, we have θ(s), θ(ps) ∈ X, thus θ(s), θ(s)θ(p) ∈ X: this contradicts the fact that X is a prefix code.

The result of Claim 2 directly leads to examine the behavior of finite complete bifix codes with regard to (anti-)automorphisms.

Finite complete bifix θ-invariant codes

At first, it is worth mentioning a well-known class of finite bifix codes: Example 5. A set X is uniform if a positive integer n exists such that X ⊆ A n . Trivially, such a set is a bifix code moreover, it is complete if, and only if, we have X = A n . It is straightforward to verify that X is invariant under every (anti-)automorphism of A * : indeed, the restriction of such a mapping on words of length n induces a permutation of A n .

It is a natural question to ask whether non-uniform finite complete bifix θ-invariant codes exist. By exhibiting infinite classes of convenient codes, the three following examples allow to bring a positive answer. Actually, the two first families of codes have been constructed by applying a famous internal transformation to some uniform code [START_REF] Césari | Sur un algorithme donnant les codes bipréfixes finis[END_REF] (cf. also [1, § 6.2]) Example 6. Let A = {a, b} and θ be the anti-automorphism of A * that is defined by

θ(a) = b, θ(b) = a. Let n = 2k + 1, with k ≥ 1. Consider the following set: X = (A n \ (Aa k b k ∪ a k b k A)) ∪ {a k b k } ∪ Aa k b k A. The set Aa k b k A is a (uniform) bifix code. Since the condition a k b k ∈ P (X) (a k b k ∈ S(X)) necessarily implies a k b k ∈ P (a k b k A) (a k b k ∈ S(Aa k b k ))
, X is a finite (non-uniform) bifix code. The code X is complete: indeed, we have Aa k b k ∩ a k b k A = ∅ therefore, given an arbitrary positive Bernoulli distribution π over A * , we have:

π(X) = π(A n \ (Aa k b k ∪ a k b k A)) + π(a k b k ) + π(Aa k b k A) = 1 -2π(a k b k ) + 2π(a k b k ) = 1.

Furthermore, since we have θ(A) = A and θ(a

k b k ) = a k b k , X is θ-invariant.
For n = 3, the preceding construction leads to the following finite complete bifix θ-invariant code [4, (1)]:

X = {a 3 , ba 2 , b 2 a, b 3 , ab, a 2 ba, a 2 b 2 , baba, bab 2 }.
Example 7. Let A = {a, b} and θ be the so-called mirror-image, which is in fact the antiautomorphism defined by

θ(a) = a, θ(b) = b. Take n = 3k + 1, with k ≥ 1. We have a k b k a k ∈ P (Aa k b k a k ) ∪ S(a k b k a k A)
; therefore an examination similar to the one we applied at Example 6 leads to verify that the following set is a finite complete bifix θ-invariant code:

X = (A n \ (Aa k b k a k ∪ a k b k a k A)) ∪ {a k b k a k } ∪ Aa k b k a k A.
For n = 4 (i.e. k = 1) the corresponding binary tree T (X) is represented in Figure 2.

We observe that, in view of constructing arbitrarily large non-uniform finite bifix θ-invariant codes over arbitrarily large finite alphabets, the two last constructions can be generalized, as illustrated by the following example:

W = i∈Z {θ i (a k b k )} = {a k b k , c k b k , c k a k , b k a k , b k c k , a k c k }.
By construction we have W ∩ (P (AW ) ∪ S(W A)) = ∅ therefore, the following set is a θ-invariant finite bifix code:

X = (A n \ (AW ∪ W A)) ∪ W ∪ AW A. (1)
Moreover, X is complete: indeed, by construction we have AW ∩ W A = ∅ therefore, for any positive Bernoulli distribution over A * , we have π(X) = 1 -2π(W ) + 2π(W ) = 1.

2) Similarly, over A = {a, b, c} take for θ the anti-automorphism onto A * defined by

θ(a) = b, θ(b) = c, θ(c) = a. Set n = 3k + 1 and W = i∈Z {θ i (a k b k a k )} = {a k b k a k , b k c k b k , c k a k c k }.
Applying the construction from (1) also leads to obtain a finite complete bifix θ-invariant code.

Non-prefix non-suffix finite complete θ-invariant codes

In the most general case, given an (anti-)automorphism θ of A * , we are looking to finite codes X ⊆ A * which are both complete and θ-invariant. With regard to the last condition, the following statement brings some characterization: Claim 3. Let θ be an (anti-)automorphism onto A * and let X be a finite subset of A * . Then X is θ-invariant if, and only if, it is the disjoint union of a finite family of uniform θ-invariant codes.

Proof. Let 1 < • • • < n be the unique increasing finite sequence of the lengths of the words in X. For each i ∈ [1, n], set X i = X ∩ A i . By construction, each set X i is a uniform code, moreover we have:

X = 1≤i≤n X i .
Clearly, the set X is θ-invariant if, and only if, for each integer i ∈ [1, n], θ induces a permutation of X i itself.

When X is a required to be a code, Claim 3 only leads to some necessary condition. For instance, the set {a, ab, b} = {a, b} ∪ {ab}, which satisfies the condition of the claim, is θ-invariant, but clearly it is not a code. Actually, despite that in any case θ-invariance is preserved with respect to the union of sets, the main obstacle is that, given two (disjoint) codes, there is no characterization that can guarantee that their union remains a code. Of course, one can wonder about the impact of θ-invariance itself on the structure of a finite complete code. Indeed, in view of the above, such an influence is very strong with regard to two special families of codes: the uniform ones and, with respect to automorphisms, the family of prefix non-suffix codes. However, the part of θ-invariance appeared in fact of lesser importance in the construction of our families of bifix codes, where it essentially involved the structure of a few convenient words (e.g. the elements of W ).

Things become even more complex when attempting to construct finite complete θinvariant codes that are neither prefix nor suffix. Indeed, with regard to finite complete codes, although that some famous families have been exhibited (e.g. [START_REF] Felice | Construction of a family of finite maximal codes[END_REF][START_REF] De Felice | Some results on finite maximal codes[END_REF]), no general structure is known. However, finite complete θ-invariant codes that are neither prefix nor suffix exist as attested by the following example: Example 9. With the anti-automorphism θ that was introduced in Example 6 (which swaps the letters a and b), consider the classical finite complete code X = {a 2 , ab, a 2 b, ab 2 , b 2 } [24, Example 2], which is neither prefix, nor suffix. It is straightforward to verify that it is θ-invariant (we have θ(ab) = ab).

Toward the construction of regular complete θ-invariant codes

In [START_REF] Restivo | On codes having no finite completion[END_REF], by making use of factorizations of the so-called cyclotomic polynomials, the author provided a family of non-finitely completable codes. It is therefore a natural question to ask whether corresponding objects exist in the framework of θ-invariant codes.

Let A be a finite alphabet, and let θ be an (anti)-automorphism of A * . Given a finite code X, if X is embeddable into a complete θ-invariant code, say Y , then, with the terminology of Remark 1, it has to be a θ-code. Indeed the set i∈Z θ i (X) is necessarily a θ-invariant code that is included in Y . Therefore, our problem comes down to wonder whether a given finite θ-invariant code can be embedded into a complete one.

We begin by strictly restraining the problem to the framework of prefix codes. Given a (non-trivial) automorphism θ, according to the preceding Claim 1 any θ-invariant prefix code can be embedded into a θ-invariant complete one. Informally, if suffices to complete the corresponding tree with convenient ones of arity |A| that are invariant under θ.

In the case of anti-automorphisms, according to Claim 2, for being embeddable into a complete one, a finite prefix θ-invariant code has to be bifix. However, the converse is false; indeed there are finite bifix θ-invariant codes that cannot be included into any complete one, as attested by the following example:

Example 10. 1) Let A = {a, b}, and be θ be the mirror anti-automorphism of Example 7. At first, we observe that the finite θ-invariant bifix code X = {aa, b} cannot embed into any finite complete bifix (not necessarily θ-invariant) code. Indeed, assume that such a complete code, say Z, exists: necessarily Z is prefix and complete, hence for any positive integer p, we have ab p ∈ P (Z * ). Therefore a positive integer n exists such that ab n belongs to Z; since b belongs to Z this contradicts the fact that Z is bifix. As a consequence X cannot be included in any finite complete prefix θ-invariant code. Indeed, according to Claim 2, such a code should be bifix.

2) Note that the infinite (regular) set Z = {b} ∪ {ab n a : n ∈ N} is a θ-invariant bifix code which contains X. Moreover, taking for π the uniform Bernoulli distribution, it is straightforward to verify that we have π(Z) = 1/2+1/4 n∈N (1/2 n ) = 1, thus Z is complete.

We do not know whether there are finite θ-invariant complete codes that contain the code X of Example 10. Actually, as far as we know, the question of embedding a finite θ-invariant code into a complete one remains open.

From another angle, the study in [START_REF] Restivo | On codes having no finite completion[END_REF] led its author to conclude that the study of all finite codes requires also investigations on the infinite ones. From that, the question of embedding a finite code into a regular one was open. A positive answer was given in [START_REF] Ehrenfeucht | Each regular code is included in a regular maximal one[END_REF], where a now famous method for embedding a regular code into a complete one was published.

From this last point of view, in the next section, we will interest in the problem of embedding a regular θ-invariant code into a regular complete one.

Embedding a regular θ-invariant code into a complete one

Some notation

In this section we consider an (anti-)automorphism θ of A * , and a non-complete θinvariant code X ⊆ A * . We ask for a complete regular θ-invariant code Y such that X ⊆ Y . We will bring a positive answer: let's begin by describing our construction.

Let X be a non-complete θ-invariant code, and let y ∈ F (X * ). Necessarily, we have |A| ≥ 2 (otherwise, X should be complete). Without loss of generality, we may assume that the initial and the terminal letters of y are different (otherwise, substitute to y the word aya, with a, a ∈ A and a = a): in particular, we have |y| ≥ 2. Set:

z = a |y| ya |y| (with y ∈ aA * a). ( 2
)
Since θ is an (anti-)automorphism, for each integer i ∈ Z, two different letters b, b exist such that the following property holds:

θ i (z) = b |y| θ i (y)b |y| (with θ i (y) ∈ bA * b). ( 3
)
Finally, we introduce the three following sets:

Z = i∈Z {θ i (z)}, (4)
W = ZA * ∩ A * Z, (5)
T = W \ (W ∪ X)(W ∪ X) + . ( 6
)
By construction, the following inclusion holds:

W ⊆ (X ∪ T ) + . ( 7
)

Basic properties of Z

By construction, each element of the preceding set Z has length 3|y|. Given two (not necessarily different) integers i, j ∈ Z, we will accurately study how the two words θ i (z), θ j (z) may overlap. overlap. Once more we are in the condition of Lemma 5.1: letters c, d, words u, v, s, t, and integers h, k exist such that the two following properties hold:

z 2 = uc h , z 1 = c h s, |u| = |s| ≥ 2|y|, h ≤ |y|, (8)
z 1 = td k , z 3 = d k v, |v| = |t| ≥ 2|y|, k ≤ |y|. (9)
It follows from uz As a direct consequence of Lemma 5.2, we obtain the following result:

1 v = z 2 xz 3 that uz 1 v = (uc h )x(d k v), thus z 1 = c h xd k . But according to ( 3
Corollary 5.3. With the preceding notation, X * Z is a prefix code.

Proof. Let z 1 , z 2 ∈ Z, x 1 , x 2 ∈ X * , u ∈ A + , such that x 1 z 1 u = x 2 z 2 .
For any word z 3 ∈ Z, we have (z 3 x 1 )z 1 (u) = z 3 x 2 z 1 , a contradiction with Lemma 5.2.

The consequences for the set

X ∪ T Lemma 5.4. The set X ∪ T is a θ-invariant code.
Proof. The fact that X ∪ T is θ-invariant comes from its construction. For proving that it is a code, we consider an arbitrary equation among the words in X ∪ T . Since X is a code, and since z / ∈ F (X * ), we may assume that at least one occurrence of a word in T appears in each side of the equation, therefore this equation takes the following form:

x 0 t 0 x 1 t 1 • • • t n-1 x n = x 0 t 0 • • • t p-1 x p , (10)
with x i , x j ∈ X * (0 ≤ i ≤ n, 0 ≤ j ≤ p) and t i , t j ∈ T (0 ≤ i ≤ n -1, 0 ≤ j ≤ p -1). Since by construction we have T ⊆ W ⊆ ZA * , each side of the equation has a prefix in X * Z.

According to Corollary 5.3 and since all the words in Z have a common length, this implies x 0 = x 0 , therefore our equation is equivalent to:

t 0 x 1 t 1 • • • t n-1 x n = t 0 x 1 • • • t p-1 x p . ( 11
)
Without loss of generality, we assume that |t 0 | ≤ |t 0 |; let k be the greatest non-negative integer such that a word s exists with t 0 x 1 t 1 • • • x k t k s = t 0 , with s ∈ A * . By contradiction, we assume s = ε. Let z 0 ∈ Z (z 1 ∈ Z) be the unique word such that t 0 ∈ A * z 0 (t k ∈ A * z 1 ). According to the preceding property (3), an integer i ∈ Z and two letters b, b exist such that z 0 = b |y| θ i (y)b |y| . Moreover, since we have y ∈ F (X * ), and since X is θ-invariant, we have θ i (y) ∈ F (X * ). By construction, the set with elements t 0 x 1 • • • t k x k+1 and t 0 is not prefix; more precisely, exactly one of the two following main conditions holds:

1. At first, we assume that t 0 ∈ P (t 0 x 1 • • • t k x k+1 ) that is, s ∈ P (x k+1 ) (cf. Figure 3). By construction, at least one of the two words s, z 0 is a suffix of the other one. Actually, since we have z 0 ∈ F (X * ), necessarily s is a proper suffix of z 0 , therefore (z 1 , z 0 ) is an overlapping pair of words. According to Lemma 5.1, necessarily we have |s| ≥ 2|y|, which implies θ i (y) ∈ F (s): a contradiction with θ i (y) ∈ F (X * ).

t k ∈ T z 1 ∈ Z z 0 ∈ Z s θ i (y)
x k+1 ∈ X * t 0 ∈ T

• •

t k ∈ T t k+1 ∈ T x k+1 ∈ X * t 0 ∈ T z 1 ∈ Z z 0 ∈ Z z 2 ∈ Z s 1

2.1

The first case corresponds to t 0 being a proper prefix of t 0 x 1 • • • t k x k+1 z 2 , that is s 1 being a proper prefix of z 2 (cf. Figure 4). With this condition, the word z 0 is necessarily a factor of z 1 x k+1 z 2 . According to Lemma 5.2, since we have s 1 = ε, this implies z 1 = z 0 , which contradicts s = ε.

2.2 It remains to consider the case where z 2 is a prefix of s 1 (cf. Figure 5). Actually, since t 0 x 1 • • • t k x k+1 z 2 is a prefix of t 0 x 1 • • • t k x k+1 s 1 = t 0 , with |z 2 | = |z 0 |, necessarily z 0 is a suffix of s 1 , hence we have s 1 ∈ z 2 A * ∩ A * z 0 , thus s 1 ∈ W according to [START_REF] Czeizler | An extension of the Lyndon-Schützenberger result to pseudoperiodic words[END_REF]. We obtain t 0 = t 0 x 1 • • • t k x k s 1 ∈ (T X * ) + W , thus t 0 ∈ (T ∪ X) + W : this contradicts [START_REF] Czeizler | On a special class of primitive words[END_REF].

In each case we obtain a contradiction: as a consequence we have s = ε, thus t 0 = t 0 x 1 • • • x k t k . Once more according to [START_REF] Czeizler | On a special class of primitive words[END_REF], it follows from t 0 ∈ T that we have k = 0, thus t 0 = t 0 . As a consequence, Equation ( 11) is equivalent to the following one:

x 1 t 1 • • • t n-1 x n = x 1 • • • t p-1 x p . ( 12
)
By iterating these arguments, we shall obtain: n = p and x i = x i , t j = t j (0 ≤ i ≤ n, 0 ≤ j ≤ n -1), therefore X ∪ T is a code: this completes the proof of Lemma 5.4.

Lemma 5.5. The code X ∪ T is complete.

Proof. Let w ∈ A * . According to the construction of W we have ZwZ ⊆ W . According to [START_REF] Deva Priya Darshini | Factors of words under an involution[END_REF] this implies ZwZ ⊆ (X ∪ T ) * , therefore we have w ∈ F ((X ∪ T ) * ).

In the case where A is a finite alphabet, the (anti-)automorphism θ is of finite order. If X is a regular code, in starting with y ∈ F (X * ), the construction in (4) leads to a finite set Z: this guarantees the regularity of the sets W and T . As a direct consequence, we obtain the following result:

Theorem 5.6. Given a non-complete θ-invariant code X ⊆ A * , the two following properties hold: (i) In any case, X can be embedded into a complete θ-invariant code in A * . (ii) If A is finite and X regular, then X can be embedded into a regular complete θinvariant code in A * .

  Regular codes are well known examples of thin codes [1, Proposition 2.5.20].

Figure 1 :

 1 Figure 1: Example 4 with n = 4. In the tree T (X), each bottom-up (top-down) branch represents an edge with label b (a).

Example 4 .

 4 Let A = {a, b}, and θ be the automorphism defined by θ(a) = b, θ(b) = a.

Figure 2 :

 2 Figure 2: Example 7: the case where n = 4, thus k = 1.

Lemma 5 . 1 .Lemma 5 . 2 .

 5152 With the notation in (3), let u, v ∈ A + , i, j ∈ Z such that |u| ≤ |z| -1 and θ i (z)v = uθ j (z). Then we have |u| = |v| ≥ 2|y|, moreover a letter b and a unique positive integer k (depending of |u|) exist such that we haveθ i (z) = ub k , θ j (z) = b k v, with k ≤ |y|.Proof. According to (3), we set θ i (z) = b |y| bx bb |y| and θ j (z) = c |y| cx cc |y| , with b, b, c, c ∈ A, b = b, c = c and |x | = |x"| = |y| -2. Since θ is an (anti-)automorphism, we have |θ i (z)| = |θ j (z)|, thus |u| = |v|; since we have 1 ≤ |u| ≤ 3|y| -1, exactly one of the following cases occurs: Case 1: 1 ≤ |u| ≤ |y| -1. With this condition, we have (θ i (z)) |u|+1 = b = c = (uθ j (z)) |u|+1 and (θ i (z)) |y|+1 = b = c = (uθ j (z)) |y|+1 , which contradicts b = b. Case 2: |u| = |y|. This condition implies (θ i (z)) |u|+1 = b = c = (uθ j (z)) |u|+1 and (θ i (z)) 2|y| = b = c = (uθ j (z)) 2|y| , which contradicts b = b. Case 3: |y| + 1 ≤ |u| ≤ 2|y| -1. We obtain (θ i (z)) 2|y| = b = c = (uθ j (z)) 2|y| and (θ i (z)) 2|y|+1 = b = c = (uθ j (z)) 2|y|+1 which contradicts b = b. Case 4: 2|y| ≤ |u| ≤ |z| -1 = 3|y| -1. With this condition, necessarily we have (θ i (z)) |u|+1 = b = c = (uθ j (z)) |u|+1 , therefore an integer k ∈ [1, |y|] exists such that θ i (z) = ub k and θ j (z) = b k v. With the preceding notation, we have A + ZA + ∩ ZX * Z = ∅. Proof. By contradiction, assume that z 1 , z 2 , z 3 ∈ Z , x ∈ X * and u, v ∈ A + exist such that uz 1 v = z 2 xz 3 . By comparing the lengths of u, v with |z|, exactly one of the three following cases occurs: Case 1: |z| ≤ |u| and |z| ≤ |v|. With this condition, we have z 2 ∈ P (u) and z 3 ∈ S(v), therefore the word z 1 is a factor of x: this contradicts Z ∩ F (X * ) = ∅. Case 2: |u| < |z| ≤ |v|. We have in fact u ∈ P (z 2 ) and z 3 ∈ S(v). We are in the condition of Lemma 5.1: the words z 2 , z 1 overlap. Consequently, u, z 1 ∈ A + and b ∈ A exist such that z 2 = ub k and z 1 = b k z 1 , with 1 ≤ k ≤ |y| and |z 1 | = |u|. But, by construction, we have |uz 1 | = |z 2 xz 3 |-|v|. Since we assume |v| ≥ |z|, this implies |uz 1 | ≤ |z 2 xz 3 |-|z| = |z 2 x|, hence we obtain uz 1 = ub k z 1 ∈ P (z 2 x). It follows from z 2 = ub k that z 1 ∈ P (x). Since we have z 1 ∈ Z and according to (3), i ∈ Z and b ∈ A exist such that we have z 1 = b k z 1 = b |y| θ i (y)b |y| . Since by Lemma 5.1 we have |z 1 | = |u| ≥ 2|y|, we obtain θ i (y) ∈ F (z 1 ), thus θ i (y) ∈ F (x), which contradicts y / ∈ F (X * ). Case 3: |v| < |z| ≤ |u|. Some similar arguments on the reversed words lead to a conclusion similar to that of Case 2. Case 4: |z| > |u| and |z| > |v|. With this condition, both the pairs of words z 2 , z 1 and z 1 , z 3 13

  ), i ∈ Z and c ∈ A exist such that we have z 1 = c |y| θ i (y)c |y| . Since we have h, k ≤ |y|, this implies d = c moreover θ i (y) is a factor of x. Once more, this contradicts y / ∈ F (X * ).

Figure 3 :

 3 Figure 3: Proof of Lemma 5.4 -the case where s ∈ P (x k+1 ).

Figure 4 :

 4 Figure 4: Proof of Lemma 5.4 -the case where x k+1 ∈ P (s) and s 1 ∈ P (z 2 ) \ {z 2 }.

Figure 5 :

 5 Figure 5: The case where x k+1 ∈ P (S), with z 2 ∈ P (s 1 ) in the proof of Lemma 5.4.

Now, we assume that t 0 x 1 • • • t k x k+1 is a proper prefix of t 0 , thus x k+1 ∈ P (s): we have s = x k+1 s 1 , with s 1 = ε. Let z 2 ∈ Z be the unique word such that t k+1 ∈ z 2 A * . By construction the set with elements t 0 x 1 • • • t k x k+1 z 2 and t 0 is not prefix. More precisely, exactly one of the two following cases occurs:

Example 11. Let A = {a, b}, and θ be the anti-automorphism such that θ(a) = b, θ(b) = a, and let X = {a 4 , a 2 b 2 , a 2 b 4 , a 4 b 2 , ba, ba 4 , b 4 a, b 4 } Trivially, X is θ-invariant. By applying Sardinas-Patterson algorithm [1, § 2.3], one can easily verify that X is a (non-prefix) code. It is non complete: by making use of the uniform Bernoulli distribution π, we obtain π(X) < 1. Let y = ba 3 ba. Firstly, we note that we have y ∈ F (X), hence y ∈ F (X * ) implies y = sp, with s ∈ S(X) and p ∈ P (X * ). Secondly, we have S(X) ∩ P (y) = {b, ba}, but since {a 3 ba, a 2 ba} ∩ P (X * ) = ∅, necessarily we have y ∈ F (X * ). Thirdly, in view of obtaining an overlapping-free word, we substitute by = b 2 a 3 ba to y (we have by ∈ F (X * ). With the notation (2, 4), we have z = a 7 b 2 a 3 bab 7 , thus:

Moreover, the sets W and T shall be constructed according to [START_REF] Czeizler | An extension of the Lyndon-Schützenberger result to pseudoperiodic words[END_REF][START_REF] Czeizler | On a special class of primitive words[END_REF].

Example 11 provides a (non-finite) regular complete θ-invariant code; in the sequel we give an example of a non-regular one:

Example 12. Let A = {a, b}, and θ be an arbitrary (anti-)automorphism of A * . Consider the famous Dyck language

Each of its elements is classically represented by a so-called Dyck path in the grid N × Z. To be more precise, with each word

a unique path is associated, namely (i, y i ) 0≤i≤n , with y 0 = y n = 0 and such that, for each i ∈ [1, n]:

By construction, D *

1 is a free submonoid of A * . Its minimal generating set is the so-called Dyck code D 1 , whose elements are represented by those of the preceding non-empty paths which satisfy the following condition:

The code D 1 is well known for being a (non-thin) complete context-free language (e.g. [START_REF] Berstel | Codes and Automata[END_REF]Example 2.5.3]). Moreover, according to Proposition 3.1, since D * 1 is θ-invariant, the same holds to the Dyck code.

As a consequence of Theorem 5.6, we obtain the following result, which states a property similar to [START_REF] Berstel | Codes and Automata[END_REF]Theorem 2.5.16] in the framework of θ-invariant code: Theorem 5.7. Given a thin θ-invariant code X ⊆ A * , the following conditions are equivalent:

(i) X is complete.

(ii) X is a maximal code.

(iii) X is maximal in the family θ-invariant codes.

(iv) A positive Bernoulli distribution π exists such that π(X) = 1.

(v) For any positive Bernoulli distribution π, we have π(X) = 1.

Proof. According to [1, Theorem 2.5.16], the conditions (i), (ii) , (iv), (v) are equivalent. Trivially, Condition (ii) implies Condition (iii). By contradiction, we prove that Condition (iii) implies Condition (i). Starting with a non-complete θ-invariant code X, according to Theorem 5.6 the existence of a complete θ-invariant code that strictly contains X is guaranteed, thus X is not maximal in the family of θ-invariant codes: this completes the proof.

Aknowledgement

We would like to thank the anonymous reviewers for their fruitful suggestions and comments.


domain: math shs

text:
Kwong-Cheong Wong
email: wongkwongcheong@gmail.com

Reasoning-and-proving in geometry in school mathematics textbooks in Hong Kong

Keywords: Reasoning-and-proving, school mathematics textbooks, geometry, Hong Kong

. Results show that Hong Kong takes the traditional but problematic approach in which proof is taught mainly in geometry and in which two-column proof is emphasized. Overall, results suggest that proof plays a marginal role in school mathematics in Hong Kong.

Introduction

In addition to verifying the truth of a mathematical statement, proof can have many other important functions in mathematics, including explanation, which can promote sense making and understanding in mathematics (de [START_REF] De Villiers | The role and function of proof in mathematics[END_REF]. As a consequence, many mathematics educators around the world, especially those in the US, recommend that proof (and proof-related reasoning) permeate school mathematics at all levels and in all content areas (e.g. [START_REF] Ball | The teaching of proof[END_REF]NCTM, 2000). Furthermore, since textbooks can have an influence on what students learn, many studies have been conducted in different national curricula (e.g. US, Israel, Australia) to examine the opportunities for students to learn reasoning and proof from school mathematics textbooks. These studies were conducted at various grade levels (e.g. middle school, high school) and content areas (e.g. algebra, geometry); for example, see [START_REF] Stylianides | Reasoning-and-proving in school mathematics textbooks[END_REF] and the articles devoted to this topic in [START_REF] Stylianides | Special Section: Reasoning-and-proving in mathematics textbooks: From the elementary to the university level[END_REF]. However, almost all of these studies were conducted in Western countries whereas only few studies have been conducted in East Asian countries (e.g. Singapore, South Korea, Hong Kong) where students have consistently performed very well in international studies of mathematics achievement such as TIMSS (e.g. [START_REF] Mullis | TIMSS 2011 International Results in Mathematics. International Association for the Evaluation of Educational Achievement[END_REF]. The present study is part of an on-going project aimed to complement the international research knowledge by examining the opportunities for students to learn reasoning and proof when they are using a popular secondary school mathematics textbook from Hong Kong. It is expected that the results obtained will shed light on how proof is being treated in school mathematics in one of those high-achieving countries (or regions) and provide insights into the influences that Chinese culture may have on issues concerning understanding in school mathematics. This paper reports our findings in geometry; for our findings in algebra, see [START_REF] Wong | Reasoning-and-proving in school mathematics textbooks: A case study from Hong Kong presented ICME13[END_REF].

The context: Hong Kong SAR

Being a special administrative region (SAR) of China, Hong Kong enjoys curriculum independence, in the sense that Hong Kong designs her own school curriculum, which is different from that in China. In 2009, Hong Kong launched her new academic structure, under which the number of years for senior secondary school changed from four years to just three years (Secondary 4, 5 and 6). Accordingly, at the same time Hong Kong initiated her New Senior Secondary Mathematics Curriculum (Education Bureau HKSARG, 2007). This new curriculum consists of two parts: the Compulsory Part and the Elective Part (also called the Extended Part). It should be pointed out that teaching proof is not one of the stated goals (or processes) of the curriculum, which mentions proof only locally in the learning targets of geometry, namely, to "formulate and write geometric proofs involving 2-dimensional shapes with appropriate symbols, terminology and reasons" (ibid, p.15). The textbook series chosen for this study is the popular New Century Mathematics (2 nd edition, [START_REF] Leung | New Century Mathematics[END_REF]. There were three reasons for choosing this textbook series: (a) this textbook series was one of the most popular ones in Hong Kong (if not the most popular one), (b) it was on the recommended booklist by the Educational Bureau, which means that it was guaranteed to be fully aligned with the new mathematics curriculum, and (c) it was coauthored by a prominent mathematics educator. Within this textbook series, there were two books (Books 4A and 4B) for Secondary 4, two books (Books 5A and 5B) for Secondary 5 and one book (Book 6) for Secondary 6. All topics in these five books were categorized into three strands: Number and Algebra, Data Handling, and Geometry (in the curriculum document (ibid.) the name "Measures, Shape and Space" was used instead).

Analytic framework and method

We followed the methodology of [START_REF] Stylianides | Reasoning-and-proving in school mathematics textbooks[END_REF] in his investigation into reasoning and proof in school mathematics textbooks in the US. The framework he used was based on his conceptualization of reasoning-and-proving (RP), a term describing the overarching activity encompassing all of the four major proof-related mathematical activities: (a) identifying patterns, (b) making conjectures, (c) providing proofs, and (d) providing non-proof arguments. As shown in Table 1 below, the first two activities were grouped into the category of making mathematical generalizations and the latter two into the category of providing support to mathematical claims. The idea behind this conceptualization was that making mathematical generalizations (identifying a pattern and conjecturing) and providing support to mathematical claims (proving) are two fundamental and interrelated aspects of doing mathematics [START_REF] Boero | Approaching theorems in grade VIII: Some mental processes underlying producing and proving conjectures, and condition suitable to enhance them[END_REF]. Further, there were two kinds of pattern: plausible and definite; two kinds of proof: generic example and demonstration; and two kinds of non-proof argument: empirical argument and rationale. For the exact definitions of these terms, see [START_REF] Stylianides | Reasoning-and-proving in school mathematics textbooks[END_REF]. In this study, we focused on the Compulsory Part of the curriculum. We examined all of the eight chapters comprising the Geometry strand (see Table 4 below for the names of these chapters). Following [START_REF] Stylianides | Reasoning-and-proving in school mathematics textbooks[END_REF], we focused on the exercises in these chapters and examined all of them. In each of these chapters, exercises were categorized under various headings: Q&A, Review Exercise, Instant Drill, Instant Drill Corner, Exercise, Supplementary Exercise, Class Activity, Inquiry & Investigation, and Unit Test. Within each category of these exercises, there were many tasks. A task here means any problem in the exercies or parts thereof that have a separate marker (Stylianides, 2009, p. 270). Task served as unit of analysis in this study and there were totally 2,929 tasks to be analyzed and categorized into the seven subcategories of the constituent activities of reasoning-and-proving set out in Table 1 above. Additionally, we extended Stylianides' framework by further dividing the subcategory "Demonstration" into seven (sub)subcategories that correspond specifically to the different proof methods that were used in the exercises of the Geometry strand of our chosen textbook series; these included (i) Proof by Definition, (ii) Proof by Calculation, (iii) Proof by Calculation and Definition, (iv) Paragraph Proof, (v) 2-Column Proof, (vi) Proof by Contradiction, and (vii) Existence Proof (see Table 3 below). To decide if a task was an RP task, we considered how it appeared in the textbook (e.g. key phrases "Prove that", "Explain your answer"). In cases where the requirements were not clear, we consulted the Teacher's Manual (which contained suggested solutions, but only suggested solutions) in order to infer what types of response was expected for students.

Reasoning-and-Proving

Examples of analysis

Although there was a considerable amount of tasks, the forms of expression of tasks providing RP opportunities were very limited. Tasks phrased with the obvious "Prove that" or "Show that" were treated as RP activities (see Examples 2, 4 and 5 below). Those tasks ending in "Explain your answer." were also treated as RP activities, because they were asking for some kind of justification (see Examples 1 and 3 below). However, in some cases there was no explicit request to explain the answer, but judging from the solutions in the Teacher's Manuals, justifications were actually expected and hence these tasks were also treated as RP activities (see Task 3 of Example 5 below). Some tasks, usually in Class Activity or Inquiry & Investigation, were special in that they were part of a template for illustrating reasoning-and-proving. Such tasks were dually coded: on the one hand as a unit of analysis on its own, and on the other hand as part of the constituent activity (or activities) of reasoning-and-proving being illustrated (see Example 5 below). Here Task 4(a) was not coded as any RP activity. Task 4(b) was coded as "Demonstration -Proof by Definition," by which we mean one-step deductive reasoning which can be derived directly from some definition (or property or theorem). This type of tasks does not involve substantive reasoningits aim is simply to check students' understanding of the definition (or property or theorem). As shown, the solution involved substitution of values into the distance formula and algebraic manipulations to calculate AC. This task was coded as "Demonstration -Proof by Calculation". This proof method is also called "Mechanical Deduction" in the literature (e.g. Reid & Knipping, 2010, p. 124). Though involving mechanical algebraic manipulations and little reasoning, logically it should be regarded as a proof (for more on this point, see Slomson, 1996, p.11, "Proofs as Calculations"). This task was coded as "Demonstration -Paragraph Proof", because it involved not just algebraic manipulations, and was written in the paragraph (or narrative) forma less formal form in which it is not required to provide justification for every step. Paragraph proofs in geometry correspond to level 2 (informal deduction) of van Hiele Levels [START_REF] Usiskin | Van Hiele levels and achievement in secondary school Geometry[END_REF]. This task was coded as "Demonstration -2-Column Proof", because it involved not just algebraic manipulations, and was written in the traditional two-column forma more formal form in which every step is required to be justified with a reason and to be presented in the rigid two-column format as shown in Figure 4 above. Two-column proofs in geometry correspond to level 3 (formal deduction) of van Hiele Levels [START_REF] Usiskin | Van Hiele levels and achievement in secondary school Geometry[END_REF]. This exercise consisted of six tasks (1, 2, 3, 4(a), 4(b) and Conclusion). It was a template for illustrating a direct proof. So these tasks were dually coded. First, each task was coded as a unit of analysis on its own. In this example, Task 3, and only Task 3, could be interpreted as an RP activity (Demonstration -Paragraph Proof or 2-Column Proof) in case the solution given in the Teacher's Manual would include a justification (e.g. "Angles in the same segment"). However, the solution given was just "C = X", so it was not regarded as a reasoning-and-proving task. Neither were the tasks 1, 2, 4(a), 4(b) and Conclusion. Then, each task was coded as part of the template illustrating RP activities. In this case, all of them were coded as "Demonstration -Paragraph Proof". For more examples, see the full version of this paper.

Results and Discussion

We have three major findings. Firstly, as shown in Table 2 below there were relatively limited opportunities (444 out of 2,929 tasks, i.e., 15.2%) for students to learn RP from the exercises of the Geometry strand of the chosen textbook series (Secondary 4 -6). The majority of these exercises were to drill procedural skills. Secondly, there was a large difference between Making Mathematical Generalizations (24 tasks) and Providing Support to Mathematical Claims (420 tasks). This suggests that these two categories of activities were treated, in large part, in isolation from each other. This is problematic as they are two fundamental and interrelated aspects of doing mathematics [START_REF] Boero | Approaching theorems in grade VIII: Some mental processes underlying producing and proving conjectures, and condition suitable to enhance them[END_REF][START_REF] Cañadas | The conjecturing process: Perspectives in theory and implications in practice[END_REF][START_REF] Hsieh | From exploration to proof production[END_REF]. Thirdly, the majority of the RP opportunities were Demonstration (364 out of 444, i.e., 82%). However, as shown in On the other hand, as shown in Table 4, 36% of the total RP tasks were concentrated in one chapter, namely, Book 4B Ch. 11 More about Basic Properties of Circlesmore specifically, in Section 11.5 Geometric Proofs on Circles, which began with "We learnt many theorems relating to properties of circles in Book 4B Chapter 10 and this chapter. In this section we will learn how to use these theorems to prove more geometric properties." In the exercises of this section, almost every task asked for a 2-column proof, suggesting that the curriculum took a traditional approach in which proof is taught mainly in geometry and in which 2-column proof is emphasized. However, this approach to proof is problematic as it gives a misrepresentation of the nature of proof in mathematics [START_REF] Wu | The role of Euclidean geometry in high school[END_REF] and its emphasis on form over meaning can lead to a shallow, syntactic kind of knowledge, rather than a connected understanding of the mathematics involved [START_REF] Schoenfeld | When good teaching leads to bad results: The disasters of 'well-taught' mathematics courses[END_REF].

Given that Hong Kong teachers rely heavily on textbooks in their teaching [START_REF] Tam | Decision making in the mathematics curricula among the Chinese mainland, Hong Kong, and Taiwan[END_REF], the above results not only confirm that in secondary school classrooms in Hong Kong students' activities mainly focus on practicing and memorizing mathematical concepts and procedures [START_REF] Leung | In search of an East Asian identity in mathematics education[END_REF], but also suggest that proof plays a marginal role in school mathematics in Hong Kong. The fact that school mathematics textbooks in Hong Kong stress drilling on procedural (or calculation) skills far more than reasoning and proof may be due to influences from Chinese culture (or, more specifically, the Confucian heritage culture or CHC). According to Leung (2006, p. 43), CHC believes that "the

  ( 1, 3) is rotated anticlockwise about the origin O through to Q1. (a) Write down the coordinates of Q1. (b) If Q1 is reflected in the x-axis to Q2, are Q and Q2 the same point? Explain your answer. Solution (from Teacher's Manual 4B, p.228): (a) Coordinates of Q1 = ( 3, 1) (b) Coordinates of Q2 = ( 3, 1) Coordinates of Q  Coordinates of Q2  Q and Q2 are not the same point.

Figure 1 :

 1 Task 4(b) of Supplementary Exercise of Ch. 12 of Book 4B

Figure 2 :

 2 Figure 2: Task 58(a) of Supplementary Exercise of Ch. 7 of Book 5B

  the figure, BM = CM = 6 cm, AM = 8 cm and AB = 10 cm. AMD is a straight line. Is AD a diameter of the circle? Explain your answer. Solution (from Teacher's Manual 4B, p.135): AM 2 + BM 2 = (8 2 + 6 2 ) cm 2 = 100 cm 2 AB 2 = 10 2 = 100 cm 2 ∵ AM 2 + BM 2 = AB 2  AMB =  AM  CB ∵ AD is the perpendicular bisector of BC.  AD passes through the centre of the circle.  AD is a diameter of the circle.

Figure 3 :

 3 Figure 3: Task 5 of Supplementary Exercise of Ch. 10 of Book 4B

Figure 4 :

 4 Figure 4: Task 11 of Exercise 11F of Ch. 11 of Book 4B

  Figure 5: Task of Inquiry & Investigation 9.1 of Ch. 9 of Book 5B

Table 1 : The analytic framework (Stylianides, 2009, p. 262)

 1

  Table 3 below, out of these 364 demonstrations, 32.1% were Proof by Definition or Proof by Calculation or Proof by Calculation andDefinition, all of which involve little reasoning. If we excluded them from Demonstration, the total RP opportunities would reduce to 11.2% (= 444  83  26  8 out of 2,929 tasks). A consequence that might be attributed to this lack of sufficient emphasis on proof even in geometry is that, as informed by TIMSS 2011(Mullis et al., 2012, p.148 & p.150), "Hong Kong students in general do well in Knowing items, and relatively badly in Reasoning items"(Leung, 2015, p. 3).

	Reasoning-and-proving subcategory	Frequency (Percent)
	I. Making Mathematical Generalizations:	24	(5.4%)
	(a) Identifying a Pattern:
	1. Plausible Pattern	0	(0.0%)
	2. Definite Pattern	12	(2.7%)
	(b) Making a Conjecture:
	3. Conjecture	12	(2.7%)
	II. Providing Support to Mathematical Claims:	420	(94.6%)
	(c) Providing a Proof:
	4. Generic Example	18	(4.1%)
	5. Demonstration	364	(82.0%)
	(d) Providing a Non-proof Argument:
	6. Empirical Argument	38	(8.6%)
	7. Rationale	0	(0.0%)
	Total:	444	(100%)

Table 2 : Frequency and Distribution of RP Tasks across RP Subcategories

 2

Proceedings of CERME10

process of learning often starts with gaining competence in the procedure, and then through repeated practice, students gain understanding." Additionally, CHC is an examination-oriented culture. In fact, the curriculum in Hong Kong is highly examination-driven. The fact that Hong Kong school mathematics textbooks stress practicing procedural (or calculation) skills far more than reasoning and proof may be a reflection of the strong influence of public examinations on textbook design. For more on how Chinese learn mathematics, see for example Fan et al. (2004).

Proof method

Frequency (Percent)