Search

We determine here the number and the list of maximal dinucleotide and trinucleotide circular codes. We prove that there is no maximal dinucleotide circular code having strictly less than 6 elements (maximum size of dinucleotide circular codes). On the other hand, a computer calculus shows that there are maximal trinucleotide circular codes with less than 20 elements (maximum size of trinucleotide circular codes). More precisely, there are maximal trinucleotide circular codes with 14, 15, 16, 17, 18 and 19 elements and no maximal trinucleotide circular code having less than 14 elements. We give the same information for the maximal self-complementary dinucleotide and trinucleotide circular codes. The amino acid distribution of maximal trinucleotide circular codes is also determined.

We begin here a combinatorial study of dinucleotide circular codes. A word written on a circle is called circular. A set of dinucleotides is a circular code if all circular words constructed with this set have a unique decomposition. Propositions based on a letter necklace allow to determine the 24 maximum dinucleotide circular codes (of 6 elements). A partition property is also identified with eight self-complementary maximum dinucleotide circular codes and two classes of eight maximum dinucleotide circular codes in bijective correspondence by the complementarity map.

We prove that a trinucleotide circular code is self-complementary if and only if its two conjugated classes are complement of each other. Using only this proposition, we prove that if a circular code is self-complementary then either both its two conjugated classes are circular codes or none is a circular code.

Recently, we identified a hierarchy relation between trinucleotide comma-free codes and trinucleotide circular codes (see our previous works). Here, we extend our hierarchy with two new classes of codes, called DLD and LDL codes, which are stronger than the comma-free codes. We also prove that no circular code with 20 trinucleotides is a DLD code and that a circular code with 20 trinucleotides is comma-free if and only if it is a LDL code. Finally, we point out the possible role of the symmetric group ∑4 in the mathematical study of trinucleotide circular codes.

In a recent paper, Michel and Pirillo prove that there are 24 dinucleotide circular codes of maximum cardinality over an alphabet of cardinality 4. In this paper we find the exact number of dinucleotide circular codes of maximum cardinality for any given (finite) cardinality of the alphabet. Moreover, we describe the structure of these codes.

Episturmian words, which include the Arnoux-Rauzy sequences, are infinite words on a finite alphabet generalizing the Sturmian words and sharing many of their same properties. This was studied in previous papers. Here we gain a deeper insight into these properties. This leads in particular to consider numerations systems similar to the Ostrowski ones and to give a matrix formula for computing the number of representations of an integer in such a system. We also obtain a complete answer to the question: if an episturmian word is morphic, which shifts of it, if any, also are morphic ?

In this paper we study infinite episturmian words which are a natural generalization of Sturmian words to an arbitrary alphabet. A characteristic property is: they are closed under reversal and have at most one right special factor of each length. They are first obtained by a construction due to de LUCA which utilizes the palindrome closure. They can also be obtained by the way of extended RAUZY rules.

An infinite word x over the alphabet A is Sturmian if and only if g x ( n ) = n + 1 for any integer n , where g x ( n ) is the number of distinct words of length n occurring in x . A palindrome is a word that can be read indistinctly from left to right or from right to left. We prove that x is Sturmian if and only if h x ( n ) = 1 + ( n mod 2) for any integer n , where h x ( n ) is the number of palindromes of length n occurring in x . An infinite word x over the alphabet A is generated by a morphism f if there exists a letter c ϵ A such that lim n →∞ f n ( c ) = x . We prove the existence of a morphism that generates the palindromes of any infinite Sturmian word generated by a morphism.

In this paper we prove that, except for at most one, all the ranks of a right infinite word which is recurrent and not ultimately periodic are the starting point of an ω -division. Using this we give a very simple proof of Shirshov's theorem. We also extend it to not necessarily finite alphabets.

We identify here a combinatorial property between circular code and genetic code. A circular code of 20 trinucleotides which allows to retrieve the reading frame has a permuted set of 20 trinucleotides which is a code, but not circular, coding the 20 amino acids in variant nuclear codes. This result is a contribution to the research field analysing the mathematical properties of genetic codes.

We give characterizations for the Rees quotients of free semigroups that have such or such combinatorial property: repetitivity, linear growth, permutation property or one of its variants.

We say that a semigroup S is (fixed-point-free, for short f.p.f.) permutable, if, for some integer n and for every x1,..., xn in S, there exists a non-trivial (fixed-point-free) permutation σ on {1,..., n}, such that: $$x_1 \ldots x_n = x_{\sigma (1)} \ldots x_{\sigma (n)} .$$ In this paper we present the results of a systematical study of fixed-point-free permutation, pointing out the main differences from the well-known permutation property for semigroup and groups (to supply an interesting example, we study into details the f.p.f. permutation property in dihedral groups). We prove, by a direct combinatorial argument, that a finitely generated periodic and fixed-point-free permutable semigroup is finite and show that a f.p.f. permutable semigroup is finite if and only if its idempotents are central. Also, f.p.f. permutable groups are characterized: a group (resp. a finitely generated group) G is f.p.f. permutable if and only if its commutator subgroup G′ is finite (resp. G is center-by-finite). Finally, we define the weak f.p.f. permutability, which is proved to be equivalent to f.p.f. permutability for groups, but not for semigroups.

In several papers Arquès and Michel studied the maximal circular codes consisting of words of length 3 (or trinucleotides) on the genetic alphabet {A, C, G, T}. We present here some additional information on these codes. In particular, we study the growth function of the self-complementary circular codes and we prove that among them exactly 528 are maximal.

The Arques-Michel autocomplementary circular codes are 216 sets of 20 trinucleotides. They have a lot of very interesting properties. Studying them, we found the following result: a set X of trinucleotides is a circular code if and only if it has no 5-necklaces.