Episturmian words: a survey
---
paper_title: Sequences With Grouped Factors

paper_content:

A connector for making electrical connection to a flexible conductor cable is disclosed which includes a block member having a first surface and a plurality of resilient electrical contact members projecting from the block member. Each of the contact members includes a portion substantially parallel to the first surface of the block member which terminates in a free end, with the parallel portions of the contact members and the first surface of the block member defining a space for receiving a flexible conductor cable to which electrical contact is to be made. The connector further includes a cover member having an inner surface. The cover member and block member are affixed together in such a manner that the inner surface of the cover member depresses the contact members in the direction of the first surface of the block member, whereby the free ends of the contact members exert a spring force against any flexible conductor cable inserted in the defined cable receiving space to make electrical contact with the flexible conductor cable and to hold the flexible conductor cable securely in the electrical connector.
---
paper_title: Palindromic factors of billiard words

paper_content:

We study palindromic factors of billiard words, in any dimension. There are differences between the two-dimensional case, and higher dimension. Arbitrary long palindrome factors exist in any dimension, but arbitrary long palindromic prefixes exist in general only in dimension 2.
---
paper_title: Fraenkel's conjecture for six sequences

paper_content:

Abstract A striking conjecture of Fraenkel asserts that every decomposition of Z >0 into m ⩾3 sets {⌊α i n+β i ⌋} n∈ Z >0 with α i and β i real, α i >1 and α i 's distinct for i =1,…, m satisfies {α 1 ,…,α m }= 2 m −1 2 k : 0⩽k . Fraenkel's conjecture was proved by Morikawa if m =3 and, under some condition, if m =4. Proofs in terms of balanced sequences have been given for m =3 by the author and for m =4 by Altman, Gaujal and Hordijk. In the present paper we use the latter approach to establish Fraenkel's conjecture for m =5 and for m =6.
---
paper_title: Coding rotations on intervals

paper_content:

We show that the coding of rotation by $\alpha$ on $m$ intervals with rationally independent lengths can be recoded over $m$ Sturmian words of angle $\alpha.$ ::: More precisely, for a given $m$ an universal automaton is constructed such that the edge indexed by the vector of values of the $i$th letter on each Sturmian word gives the value of the $i$th letter of the coding of rotation.
---
paper_title: A generalization of Sturmian sequences; combinatorial structure and transcendence

paper_content:

We investigate a class of minimal sequences on a finite alphabet Ak = {1,2,...,k} having (k - 1)n + 1 distinct subwords of length n. These sequences, originally defined by P. Arnoux and G. Rauzy, are a natural generalization of binary Sturmian sequences. We describe two simple combinatorial algorithms for constructing characteristic Arnoux-Rauzy sequences (one of which is new even in the Sturmian case). Arnoux-Rauzy sequences arising from fixed points of primitive morphisms are characterized by an underlying periodic structure. We show that every Arnoux-Rauzy sequence contains arbitrarily large subwords of the form V^2+e and, in the Sturmian case, arbitrarily large subwords of the form V^3+e. Finally, we prove that an irrational number whose base b-digit expansion is an Arnoux-Rauzy sequence is transcendental.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Three distance theorems and combinatorics on words

paper_content:

The aim of this paper is to investigate the connection between some generalizations of the three distance theorem and combinatorics on words for sequences defined as codings of irrational rotations on the unit circle. We also give some new results concerning the frequencies of factors for such sequences.
---
paper_title: Automatic Sequences: Theory, Applications, Generalizations

paper_content:

Preface 1. Stringology 2. Number theory and algebra 3. Numeration systems 4. Finite automata and other models of computation 5. Automatic sequences 6. Uniform morphisms and automatic sequences 7. Morphic sequences 8. Frequency of letters 9. Characteristic words 10. Subwords 11. Cobham's theorem 12. Formal power series 13. Automatic real numbers 14. Multidimensional automatic sequences 15. Automaticity 16. k-regular sequences 17. Physics Appendix. Hints, references and solutions for selected exercises Bibliography Index.
---
paper_title: Balances for fixed points of primitive substitutions

paper_content:

An infinite word defined over a finite alphabet A is balanced if for any pair (ω,ω') of factors of the same length and for any letter a in the alphabet ||ω|a - |ω'|a| ≤ 1, where |ω|a denotes the number of occurrences of the letter a in the word ω. In this paper, we generalize this notion and introduce a measure of balance for an infinite sequence. In the case of fixed points of primitive substitutions, we show that the asymptotic behaviour of this measure is in part ruled by the spectrum of the incidence matrix associated with the substitution. Connections with frequencies of letters and other balance properties are also discussed.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: Transcendence of Sturmian or morphic continued fractions

paper_content:

Abstract We prove, using a theorem of W. Schmidt, that if the sequence of partial quotients of the continued fraction expansion of a positive irrational real number takes only two values, and begins with arbitrary long blocks which are “almost squares,” then this number is either quadratic or transcendental. This result applies in particular to real numbers whose partial quotients form a Sturmian (or quasi-Sturmian) sequence, or are given by the sequence (1+(⌊ nα ⌋ mod 2)) n ⩾0 , or are a “repetitive” fixed point of a binary morphism satisfying some technical conditions.
---
paper_title: Generalized balances in Sturmian words

paper_content:

One of the numerous characterizations of Sturmian words is based on the notion of balance. An infinite word X on the {0, 1} alphabet is balanced if, given two factors of X, w and w', having the same length, the difference between the number of 0's in w (denoted by |w|0) and the number of 0's in w' is at most 1, i.e. ||w|0 - |w'|0| ≤ 1. It is well known that an aperiodic word is Sturmian if and only if it is balanced.In this paper, the balance notion is generalized by considering the number of occurrences of a word u in w (denoted by |w|u,) and w'. The following is obtained. Theorem. Let x be a Sturmian word. Let u, w and w' be three factors of x. Then, |w| = |w'| ⇒ ||w|u - |w'|u| ≤ |u|.Another balance property, called equilibrium, is also given. This notion permits us to give a new characterization of Sturmian words. The main techniques used in the proofs are word graphs and return words.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: Characterizations of finite and infinite episturmian words via lexicographic orderings

paper_content:

In this talk, I will present some new results arising from collaborative work with Jacques Justin (France) and Giuseppe Pirillo (Italy). This work, which extends previous results on extremal properties of infinite Sturmian and episturmian words, is purely combinatorial in nature. Specifically, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.
---
paper_title: EPISTURMIAN WORDS: SHIFTS, MORPHISMS AND NUMERATION SYSTEMS

paper_content:

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 ?
---
paper_title: Sturmian words: structure, combinatorics, and their arithmetics

paper_content:

Abstract We prove some new results concerning the structure, the combinatorics and the arithmetics of the set PER of all the words w having two periods p and q, p ⩽ q , which are coprimes and such that ¦w¦= p + q− 2 . A basic theorem relating PER with the set of finite standard Sturmian words was proved in de Luca and Mignosi (1994). The main result of this paper is the following simple inductive definition of PER : the empty word belongs to PER , If w is an already constructed word of PER , then also ( aw ) (−) and ( bw ) (−) belong to PER , where (−) denotes the operator of palindrome left-closure, i.e. it associates to each word u the smallest palindrome word u (−) having u as a suffix. We show that, by this result, one can construct in a simple way all finite and infinite standard Sturmian words. We prove also that, up to the automorphism which interchanges the letter a with the letter b, any element of PER can be codified by the irreducible fraction p q . This allows us to construct for any n ⩾0 a natural bijection, that we call Farey correspondence, of the set of the Farey series of order n + 1 and the set of special elements of length n of the set St of all finite Sturmian words. Finally, we introduce the concepts of Farey tree and Farey monoid. This latter is obtained by defining a suitable product operation on the developments in continued fractions of the set of all irreducible fractions p q .
---
paper_title: Episturmian morphisms and a Galois theorem on continued fractions

paper_content:

We associate with a word w on a finite alphabet A an episturmian (or Arnoux-Rauzy) morphism and a palindrome. We study their relations with the similar ones for the reversal of w . Then when |A|=2 we deduce, using the Sturmian words that are the fixed points of the two morphisms, a proof of a Galois theorem on purely periodic continued fractions whose periods are the reversal of each other.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: Characterizations of finite and infinite episturmian words via lexicographic orderings

paper_content:

In this talk, I will present some new results arising from collaborative work with Jacques Justin (France) and Giuseppe Pirillo (Italy). This work, which extends previous results on extremal properties of infinite Sturmian and episturmian words, is purely combinatorial in nature. Specifically, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.
---
paper_title: Quasiperiodic and Lyndon episturmian words

paper_content:

Recently the second two authors characterized quasiperiodic Sturmian words, proving that a Sturmian word is non-quasiperiodic if and only if, it is an infinite Lyndon word. Here we extend this study to episturmian words (a natural generalization of Sturmian words) by describing all the quasiperiods of an episturmian word, which yields a characterization of quasiperiodic episturmian words in terms of their directive words. Even further, we establish a complete characterization of all episturmian words that are Lyndon words. Our main results show that, unlike the Sturmian case, there is a much wider class of episturmian words that are non-quasiperiodic, besides those that are infinite Lyndon words. Our key tools are morphisms and directive words, in particular normalized directive words, which we introduced in an earlier paper. Also of importance is the use of return words to characterize quasiperiodic episturmian words, since such a method could be useful in other contexts.
---
paper_title: A local balance property of episturmian words

paper_content:

We prove that episturmian words and Arnoux-Rauzy sequences can be characterized using a local balance property. We also give a new characterization of epistandard words.
---
paper_title: On Sturmian and episturmian words, and related topics

paper_content:

Combinatorics on words plays a fundamental role in various fields of mathematics, not to mention its relevance in theoretical computer science and physics. Most renowned among its branches is the theory of infinite binary sequences called Sturmian words, which are fascinating in many respects, having been studied from combinatorial, algebraic, and geometric points of view. The most well-known example of a Sturmian word is the ubiquitous Fibonacci word, the importance of which lies in combinatorial pattern matching and the theory of words. Properties of the Fibonacci word and, more generally, Sturmian words have been extensively studied, not only because of their significance in discrete mathematics, but also due to their practical applications in computer imagery (digital straightness), theoretical physics (quasicrystal modelling) and molecular biology.
---
paper_title: Powers in a class of A-strict standard episturmian words

paper_content:

This paper concerns a specific class of strict standard episturmian words whose directive words resemble those of characteristic Sturmian words. In particular, we explicitly determine all integer powers occurring in such infinite words, extending recent results of Damanik and Lenz [D. Damanik, D. Lenz, Powers in Sturmian sequences, European J. Combin. 24 (2003) 377-390, doi:10.1016/S0195-6698(03)00026-X], who studied powers in Sturmian words. The key tools in our analysis are canonical decompositions and a generalization of singular words, which were originally defined for the ubiquitous Fibonacci word. Our main results are demonstrated via some examples, including the k-bonacci word, a generalization of the Fibonacci word to a k-letter alphabet (k>=2).
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: Some properties of the Tribonacci sequence

paper_content:

In this paper, we consider the factor properties of the Tribonacci sequence. We define the singular words, and then give the singular factorization and the Lyndon factorization. As applications, we study the powers of the factors and the overlap of the factors. We also calculate the free index of the sequence.
---
paper_title: Conjugacy and episturmian morphisms

paper_content:

Episturmian morphisms generalize Sturmian morphisms. Here, we study some intrinsic properties of these morphisms: invertibility, presentation, cancellativity, unitarity, characterization by conjugacy. Most of them are generalizations of known properties of Sturmian morphisms. But we present also some results on episturmian morphisms that have not already been stated in the particular case of Sturmian morphisms: characterization of the episturmian morphisms that preserve palindromes, new algorithms to compute conjugates.We also study the conjugation of morphisms in the general case and show that the monoid of invertible morphisms on an alphabet containing at least three letters is not finitely generated.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: A connection between palindromic and factor complexity using return words

paper_content:

In this paper we prove that for any infinite word W whose set of factors is closed under reversal, the following conditions are equivalent: (I) all complete returns to palindromes are palindromes; (II) P(n) + P(n+1) = C(n+1) - C(n) + 2 for all n, where P (resp. C) denotes the palindromic complexity (resp. factor complexity) function of W, which counts the number of distinct palindromic factors (resp. factors) of each length in W.
---
paper_title: EPISTURMIAN WORDS: SHIFTS, MORPHISMS AND NUMERATION SYSTEMS

paper_content:

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 ?
---
paper_title: A generalization of Sturmian sequences; combinatorial structure and transcendence

paper_content:

We investigate a class of minimal sequences on a finite alphabet Ak = {1,2,...,k} having (k - 1)n + 1 distinct subwords of length n. These sequences, originally defined by P. Arnoux and G. Rauzy, are a natural generalization of binary Sturmian sequences. We describe two simple combinatorial algorithms for constructing characteristic Arnoux-Rauzy sequences (one of which is new even in the Sturmian case). Arnoux-Rauzy sequences arising from fixed points of primitive morphisms are characterized by an underlying periodic structure. We show that every Arnoux-Rauzy sequence contains arbitrarily large subwords of the form V^2+e and, in the Sturmian case, arbitrarily large subwords of the form V^3+e. Finally, we prove that an irrational number whose base b-digit expansion is an Arnoux-Rauzy sequence is transcendental.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: On a characteristic property of ARNOUX–RAUZY sequences

paper_content:

Here we give a characterization of Arnoux-Rauzy sequences by the way of the lexicographic orderings of their alphabet.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: A characterization of Sturmian morphisms

paper_content:

A morphism is called Sturmian if it preserves all Sturmian (infinite) words. It is weakly Sturmian if it preserves at least one Sturmian word. We prove that a morphism is Sturmian if and only if it keeps the word ba2ba2baba2bab balanced. As a consequence, weakly Sturmian morphisms are Sturmian. An application to infinite words associated to irrational numbers is given.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: On Sturmian and episturmian words, and related topics

paper_content:

Combinatorics on words plays a fundamental role in various fields of mathematics, not to mention its relevance in theoretical computer science and physics. Most renowned among its branches is the theory of infinite binary sequences called Sturmian words, which are fascinating in many respects, having been studied from combinatorial, algebraic, and geometric points of view. The most well-known example of a Sturmian word is the ubiquitous Fibonacci word, the importance of which lies in combinatorial pattern matching and the theory of words. Properties of the Fibonacci word and, more generally, Sturmian words have been extensively studied, not only because of their significance in discrete mathematics, but also due to their practical applications in computer imagery (digital straightness), theoretical physics (quasicrystal modelling) and molecular biology.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Some remarks on invertible substitutions on three letter alphabet

paper_content:

By introducing the notion of “prime substitution” it is shown that the set of invertible substitutions over an alphabet of more than three letters is not finitely generated. Some examples are given.
---
paper_title: On Morphisms Preserving Infinite Lyndon Words

paper_content:

In a previous paper, we characterized free monoid morphisms preserving finite Lyndon words. In particular, we proved that such a morphism preserves the order on finite words. Here we study morphisms preserving infinite Lyndon words and morphisms preserving the order on infinite words. We characterize them and show relations with morphisms preserving Lyndon words or the order on finite words. We also briefly study morphisms preserving border-free words and those preserving the radix order.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: Conjugacy and episturmian morphisms

paper_content:

Episturmian morphisms generalize Sturmian morphisms. Here, we study some intrinsic properties of these morphisms: invertibility, presentation, cancellativity, unitarity, characterization by conjugacy. Most of them are generalizations of known properties of Sturmian morphisms. But we present also some results on episturmian morphisms that have not already been stated in the particular case of Sturmian morphisms: characterization of the episturmian morphisms that preserve palindromes, new algorithms to compute conjugates.We also study the conjugation of morphisms in the general case and show that the monoid of invertible morphisms on an alphabet containing at least three letters is not finitely generated.
---
paper_title: Complexity of sequences and dynamical systems

paper_content:

Abstract This is a survey of recent results on the notion of symbolic complexity, which counts the number of factors of an infinite sequence, particularly in view of its relations with dynamical systems.
---
paper_title: A local balance property of episturmian words

paper_content:

We prove that episturmian words and Arnoux-Rauzy sequences can be characterized using a local balance property. We also give a new characterization of epistandard words.
---
paper_title: Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words

paper_content:

Using the notions of conjugacy of morphisms and of morphisms preserving Lyndon words, we answer a question of G. Melancon. We characterize cases where the sequence of Lyndon words in the Lyndon factorization of a standard Sturmian word is morphic. In each possible case, the corresponding morphism is given.
---
paper_title: A generalization of Sturmian sequences; combinatorial structure and transcendence

paper_content:

We investigate a class of minimal sequences on a finite alphabet Ak = {1,2,...,k} having (k - 1)n + 1 distinct subwords of length n. These sequences, originally defined by P. Arnoux and G. Rauzy, are a natural generalization of binary Sturmian sequences. We describe two simple combinatorial algorithms for constructing characteristic Arnoux-Rauzy sequences (one of which is new even in the Sturmian case). Arnoux-Rauzy sequences arising from fixed points of primitive morphisms are characterized by an underlying periodic structure. We show that every Arnoux-Rauzy sequence contains arbitrarily large subwords of the form V^2+e and, in the Sturmian case, arbitrarily large subwords of the form V^3+e. Finally, we prove that an irrational number whose base b-digit expansion is an Arnoux-Rauzy sequence is transcendental.
---
paper_title: Initial powers of Sturmian sequences

paper_content:

In this paper we investigate powers of prefixes of Sturmian sequences. We give an explicit formula for ice(ω), the initial critical exponent of a Sturmian sequence ω, defined as the supremum of all real numbers p > 0 for which there exist arbitrary long prefixes of ω of the form up, in terms of its S-adic representation. This formula is based on Ostrowski's numeration system. Furthermore we characterize those irrational slopes α of which there exists a Sturmian sequence ω beginning in only finitely many powers of 2 + e, that is for which ice(ω) = 2. In the process we recover the known results for the index (or critical exponent) of a Sturmian sequence. We also focus on the Fibonacci Sturmian shift and prove that the set of Sturmian sequences with ice strictly smaller than its everywhere value has Hausdorff dimension 1.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Balances for fixed points of primitive substitutions

paper_content:

An infinite word defined over a finite alphabet A is balanced if for any pair (ω,ω') of factors of the same length and for any letter a in the alphabet ||ω|a - |ω'|a| ≤ 1, where |ω|a denotes the number of occurrences of the letter a in the word ω. In this paper, we generalize this notion and introduce a measure of balance for an infinite sequence. In the case of fixed points of primitive substitutions, we show that the asymptotic behaviour of this measure is in part ruled by the spectrum of the incidence matrix associated with the substitution. Connections with frequencies of letters and other balance properties are also discussed.
---
paper_title: Quasiperiodic Sturmian words and morphisms

paper_content:

We characterize all quasiperiodic Sturmian words: a Sturmian word is not quasiperiodic if and only if it is a Lyndon word. Moreover, we study links between Sturmian morphisms and quasiperiodicity.
---
paper_title: A characterization of fine words over a finite alphabet

paper_content:

To any infinite word w over a finite alphabet A we can associate two infinite words min(w) and max(w) such that any prefix of min(w) (resp. max(w)) is the lexicographically smallest (resp. greatest) amongst the factors of w of the same length. We say that an infinite word w over A is"fine"if there exists an infinite word u such that, for any lexicographic order, min(w) = au where a = min(A). In this paper, we characterize fine words; specifically, we prove that an infinite word w is fine if and only if w is either a"strict episturmian word"or a strict"skew episturmian word''. This characterization generalizes a recent result of G. Pirillo, who proved that a fine word over a 2-letter alphabet is either an (aperiodic) Sturmian word, or an ultimately periodic (but not periodic) infinite word, all of whose factors are (finite) Sturmian.
---
paper_title: EPISTURMIAN WORDS: SHIFTS, MORPHISMS AND NUMERATION SYSTEMS

paper_content:

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 ?
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Balances for fixed points of primitive substitutions

paper_content:

An infinite word defined over a finite alphabet A is balanced if for any pair (ω,ω') of factors of the same length and for any letter a in the alphabet ||ω|a - |ω'|a| ≤ 1, where |ω|a denotes the number of occurrences of the letter a in the word ω. In this paper, we generalize this notion and introduce a measure of balance for an infinite sequence. In the case of fixed points of primitive substitutions, we show that the asymptotic behaviour of this measure is in part ruled by the spectrum of the incidence matrix associated with the substitution. Connections with frequencies of letters and other balance properties are also discussed.
---
paper_title: Conjugacy and episturmian morphisms

paper_content:

Episturmian morphisms generalize Sturmian morphisms. Here, we study some intrinsic properties of these morphisms: invertibility, presentation, cancellativity, unitarity, characterization by conjugacy. Most of them are generalizations of known properties of Sturmian morphisms. But we present also some results on episturmian morphisms that have not already been stated in the particular case of Sturmian morphisms: characterization of the episturmian morphisms that preserve palindromes, new algorithms to compute conjugates.We also study the conjugation of morphisms in the general case and show that the monoid of invertible morphisms on an alphabet containing at least three letters is not finitely generated.
---
paper_title: EPISTURMIAN WORDS: SHIFTS, MORPHISMS AND NUMERATION SYSTEMS

paper_content:

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 ?
---
paper_title: Directive words of episturmian words: equivalences and normalization

paper_content:

Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence of these results, we characterize episturmian words having a unique directive word.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: EPISTURMIAN WORDS: SHIFTS, MORPHISMS AND NUMERATION SYSTEMS

paper_content:

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 ?
---
paper_title: Directive words of episturmian words: equivalences and normalization

paper_content:

Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence of these results, we characterize episturmian words having a unique directive word.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Conjugacy and episturmian morphisms

paper_content:

Episturmian morphisms generalize Sturmian morphisms. Here, we study some intrinsic properties of these morphisms: invertibility, presentation, cancellativity, unitarity, characterization by conjugacy. Most of them are generalizations of known properties of Sturmian morphisms. But we present also some results on episturmian morphisms that have not already been stated in the particular case of Sturmian morphisms: characterization of the episturmian morphisms that preserve palindromes, new algorithms to compute conjugates.We also study the conjugation of morphisms in the general case and show that the monoid of invertible morphisms on an alphabet containing at least three letters is not finitely generated.
---
paper_title: EPISTURMIAN WORDS: SHIFTS, MORPHISMS AND NUMERATION SYSTEMS

paper_content:

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 ?
---
paper_title: Quasiperiodic and Lyndon episturmian words

paper_content:

Recently the second two authors characterized quasiperiodic Sturmian words, proving that a Sturmian word is non-quasiperiodic if and only if, it is an infinite Lyndon word. Here we extend this study to episturmian words (a natural generalization of Sturmian words) by describing all the quasiperiods of an episturmian word, which yields a characterization of quasiperiodic episturmian words in terms of their directive words. Even further, we establish a complete characterization of all episturmian words that are Lyndon words. Our main results show that, unlike the Sturmian case, there is a much wider class of episturmian words that are non-quasiperiodic, besides those that are infinite Lyndon words. Our key tools are morphisms and directive words, in particular normalized directive words, which we introduced in an earlier paper. Also of importance is the use of return words to characterize quasiperiodic episturmian words, since such a method could be useful in other contexts.
---
paper_title: Directive words of episturmian words: equivalences and normalization

paper_content:

Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence of these results, we characterize episturmian words having a unique directive word.
---
paper_title: Inequalities characterizing standard Sturmian and episturmian words

paper_content:

Considering the smallest and the greatest factors with respect to the lexicographic order we associate to each infinite word r two other infinite words min(r) and max(r). In this paper we prove that the inequalities as ≤ min(s) ≤ max(s) ≤ bs characterize standard Sturmian words (proper ones and periodic ones) and that the condition "for any x ∈ A and lexicographic order < satisfying x = min(A) one has xs ≤ min(s)" characterizes standard episturmian words.
---
paper_title: Characterisations of Balanced Words via Orderings

paper_content:

Three new characterisations of balanced words are presented. Each of these characterisations is based on the ordering of a shift orbit, either lexicographically or with respect to the norm |ċ|1 (which counts the number of occurrences of the symbol 1).
---
paper_title: Initial powers of Sturmian sequences

paper_content:

In this paper we investigate powers of prefixes of Sturmian sequences. We give an explicit formula for ice(ω), the initial critical exponent of a Sturmian sequence ω, defined as the supremum of all real numbers p > 0 for which there exist arbitrary long prefixes of ω of the form up, in terms of its S-adic representation. This formula is based on Ostrowski's numeration system. Furthermore we characterize those irrational slopes α of which there exists a Sturmian sequence ω beginning in only finitely many powers of 2 + e, that is for which ice(ω) = 2. In the process we recover the known results for the index (or critical exponent) of a Sturmian sequence. We also focus on the Fibonacci Sturmian shift and prove that the set of Sturmian sequences with ice strictly smaller than its everywhere value has Hausdorff dimension 1.
---
paper_title: A characterization of fine words over a finite alphabet

paper_content:

To any infinite word w over a finite alphabet A we can associate two infinite words min(w) and max(w) such that any prefix of min(w) (resp. max(w)) is the lexicographically smallest (resp. greatest) amongst the factors of w of the same length. We say that an infinite word w over A is"fine"if there exists an infinite word u such that, for any lexicographic order, min(w) = au where a = min(A). In this paper, we characterize fine words; specifically, we prove that an infinite word w is fine if and only if w is either a"strict episturmian word"or a strict"skew episturmian word''. This characterization generalizes a recent result of G. Pirillo, who proved that a fine word over a 2-letter alphabet is either an (aperiodic) Sturmian word, or an ultimately periodic (but not periodic) infinite word, all of whose factors are (finite) Sturmian.
---
paper_title: Palindromic Richness

paper_content:

In this paper, we study combinatorial and structural properties of a new class of finite and infinite words that are 'rich' in palindromes in the utmost sense. A characteristic property of so-called"rich words"is that all complete returns to any palindromic factor are themselves palindromes. These words encompass the well-known episturmian words, originally introduced by the second author together with X. Droubay and G. Pirillo in 2001. Other examples of rich words have appeared in many different contexts. Here we present the first unified approach to the study of this intriguing family of words. Amongst our main results, we give an explicit description of the periodic rich infinite words and show that the recurrent balanced rich infinite words coincide with the balanced episturmian words. We also consider two wider classes of infinite words, namely"weakly rich words"and almost rich words (both strictly contain all rich words, but neither one is contained in the other). In particular, we classify all recurrent balanced weakly rich words. As a consequence, we show that any such word on at least three letters is necessarily episturmian; hence weakly rich words obey Fraenkel's conjecture. Likewise, we prove that a certain class of almost rich words obeys Fraenkel's conjecture by showing that the recurrent balanced ones are episturmian or contain at least two distinct letters with the same frequency. Lastly, we study the action of morphisms on (almost) rich words with particular interest in morphisms that preserve (almost) richness. Such morphisms belong to the class of"P-morphisms"that was introduced by A. Hof, O. Knill, and B. Simon in 1995.
---
paper_title: On a characteristic property of ARNOUX–RAUZY sequences

paper_content:

Here we give a characterization of Arnoux-Rauzy sequences by the way of the lexicographic orderings of their alphabet.
---
paper_title: Morse and Hedlund’s Skew Sturmian Words Revisited

paper_content:

For any infinite word r over A = {a, b} we associate two infinite words min(r), max(r) such that any prefix of min(r) (max(r), respectively) is the lexicographically smallest (greatest, respectively) among the factors of r of the same length. We prove that (min(r); max(r)) = (as, bs) for some infinite word s if and only if r is a proper Sturmian word or an ultimately periodic word of a particular form. This result is based on a lemma concerning sequences of infinite words.
---
paper_title: Characterizations of finite and infinite episturmian words via lexicographic orderings

paper_content:

In this talk, I will present some new results arising from collaborative work with Jacques Justin (France) and Giuseppe Pirillo (Italy). This work, which extends previous results on extremal properties of infinite Sturmian and episturmian words, is purely combinatorial in nature. Specifically, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.
---
paper_title: A characterization of Sturmian morphisms

paper_content:

A morphism is called Sturmian if it preserves all Sturmian (infinite) words. It is weakly Sturmian if it preserves at least one Sturmian word. We prove that a morphism is Sturmian if and only if it keeps the word ba2ba2baba2bab balanced. As a consequence, weakly Sturmian morphisms are Sturmian. An application to infinite words associated to irrational numbers is given.
---
paper_title: EPISTURMIAN WORDS: SHIFTS, MORPHISMS AND NUMERATION SYSTEMS

paper_content:

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 ?
---
paper_title: On substitution invariant Sturmian words: An application of Rauzy fractals

paper_content:

Sturmian words are infinite words that have exactly n + 1 factors of length n for every positive integer n. A Sturmian word s�,� is also defined as a coding over a two-letter alphabet of the orbit of the pointunder the action of the irrational rotation R� : x 7! x + � (mod 1). Yasutomi characterized in (34) all the pairs (�,�) such that the Sturmian word s�,� is a fixed point of some non-trivial substitution. By investigating the Rauzy frac- tals associated with invertible substitutions, we give an alternative geometric proof of Yasutomi's characterization.
---
paper_title: A remark on morphic sturmian words

paper_content:

This Note deals with binary Sturmian words that are morphic, i.e. generated by iterating a morphism. Among these, characteristic words are a well-known subclass. We prove that for every characteristic morphic word x, the four words ax, bx, abx and bax are morphic
---
paper_title: A little more about morphic Sturmian words

paper_content:

Among Sturmian words, some of them are morphic, i.e. fixed point of a non-identical morphism on words. Berstel and Seebold (1993) have shown that if a characteristic Sturmian word is morphic, then it can be extended by the left with one or two letters in such a way that it remains morphic and Sturmian. Yasutomi (1997) has proved that these were the sole possible additions and that, if we cut the first letters of such a word, it didn't remain morphic. In this paper, we give an elementary and combinatorial proof of this result.
---
paper_title: EPISTURMIAN WORDS: SHIFTS, MORPHISMS AND NUMERATION SYSTEMS

paper_content:

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 ?
---
paper_title: A generalization of Sturmian sequences; combinatorial structure and transcendence

paper_content:

We investigate a class of minimal sequences on a finite alphabet Ak = {1,2,...,k} having (k - 1)n + 1 distinct subwords of length n. These sequences, originally defined by P. Arnoux and G. Rauzy, are a natural generalization of binary Sturmian sequences. We describe two simple combinatorial algorithms for constructing characteristic Arnoux-Rauzy sequences (one of which is new even in the Sturmian case). Arnoux-Rauzy sequences arising from fixed points of primitive morphisms are characterized by an underlying periodic structure. We show that every Arnoux-Rauzy sequence contains arbitrarily large subwords of the form V^2+e and, in the Sturmian case, arbitrarily large subwords of the form V^3+e. Finally, we prove that an irrational number whose base b-digit expansion is an Arnoux-Rauzy sequence is transcendental.
---
paper_title: Pisot substitutions and Rauzy fractals

paper_content:

We prove that the dynamical system generated by a primitive unimodular substitution of the Pisot type ond letters satisfying a combinatorial condition which is easy to check, is measurably isomorphic to a domain exchange in R d 1 , and is a nite extension of a translation on the torus T d 1 .I n the course of the proof, we introduce some potentially useful notions: the linear maps associated to a substitution and their dual maps, and the -structure for a dynamical system with respect to a pair of partitions.
---
paper_title: COMBINATORIAL PROPERTIES OF ARNOUX–RAUZY SUBSHIFTS AND APPLICATIONS TO SCHRÖDINGER OPERATORS

paper_content:

We consider Arnoux–Rauzy subshifts X and study various combinatorial questions: When is X linearly recurrent? What is the maximal power occurring in X? What is the number of palindromes of a given length occurring in X? We present applications of our combinatorial results to the spectral theory of discrete one-dimensional Schrodinger operators with potentials given by Arnoux–Rauzy sequences.
---
paper_title: RECENT RESULTS ON EXTENSIONS OF STURMIAN WORDS

paper_content:

Sturmian words are infinite words over a two-letter alphabet that admit a great number of equivalent definitions. Most of them have been given in the past ten years. Among several extensions of Sturmian words to larger alphabets, the Arnoux–Rauzy words appear to share many of the properties of Sturmian words. In this survey, combinatorial properties of these two families are considered and compared.
---
paper_title: STRUCTURE OF THREE INTERVAL EXCHANGE TRANSFORMATIONS I : AN ARITHMETIC STUDY

paper_content:

Dans cet article nous decrivons une generalisation a la dimension 2 de l'algorithme d'Euclide, qui provient de la dynamique des echanges de 3 intervalles. Nous examinons diverses proprietes diophantiennes de cet algorithme, en particulier la, qualite de l'approximation simultanee. Nous montrons qu'il verifie un theoreme de type Lagrange : l'algorithme est finalement periodique si et seulement si les parametres sont dans la meme extension quadratique de Q.
---
paper_title: Fine and Wilf's theorem for three periods and a generalization of Sturmian words

paper_content:

We extend the theorem of Fine and Wilf to words having three periods. We then define the set 3-PER of words of maximal length for which such result does not apply. We prove that the set 3-PER and the sequences of complexity 2n + 1, introduced by Arnoux and Rauzy to generalize Sturmian words, have the same set of factors.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: Characterizations of finite and infinite episturmian words via lexicographic orderings

paper_content:

In this talk, I will present some new results arising from collaborative work with Jacques Justin (France) and Giuseppe Pirillo (Italy). This work, which extends previous results on extremal properties of infinite Sturmian and episturmian words, is purely combinatorial in nature. Specifically, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Palindromes and Sturmian words

paper_content:

Abstract 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.
---
paper_title: Palindromes and Sturmian words

paper_content:

Abstract 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.
---
paper_title: Frequencies of factors in Arnoux-Rauzy sequences

paper_content:

V. Berthe showed that the frequencies of factors in a Sturmian word of slope α, as well as the number of factors with a given frequency, can be expressed in terms of the continued fraction expansion of α. In this paper we describe a multi-dimensional continued fraction process associated with a class of sequences of (block) complexity kn+1 originally introduced by P. Arnoux and G. Rauzy. This vectorial division algorithm yields simultaneous rational approximations of the frequencies of the letters. We extend Berthe’s result to factors of Arnoux-Rauzy sequences by expressing both the frequencies and the number of factors with a given frequency, in terms of the ‘convergents’ obtained from the generalized continued fraction expansion of the frequencies of the letters.
---
paper_title: Episturmian morphisms and a Galois theorem on continued fractions

paper_content:

We associate with a word w on a finite alphabet A an episturmian (or Arnoux-Rauzy) morphism and a palindrome. We study their relations with the similar ones for the reversal of w . Then when |A|=2 we deduce, using the Sturmian words that are the fixed points of the two morphisms, a proof of a Galois theorem on purely periodic continued fractions whose periods are the reversal of each other.
---
paper_title: A generalization of Sturmian sequences; combinatorial structure and transcendence

paper_content:

We investigate a class of minimal sequences on a finite alphabet Ak = {1,2,...,k} having (k - 1)n + 1 distinct subwords of length n. These sequences, originally defined by P. Arnoux and G. Rauzy, are a natural generalization of binary Sturmian sequences. We describe two simple combinatorial algorithms for constructing characteristic Arnoux-Rauzy sequences (one of which is new even in the Sturmian case). Arnoux-Rauzy sequences arising from fixed points of primitive morphisms are characterized by an underlying periodic structure. We show that every Arnoux-Rauzy sequence contains arbitrarily large subwords of the form V^2+e and, in the Sturmian case, arbitrarily large subwords of the form V^3+e. Finally, we prove that an irrational number whose base b-digit expansion is an Arnoux-Rauzy sequence is transcendental.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: EPISTURMIAN WORDS: SHIFTS, MORPHISMS AND NUMERATION SYSTEMS

paper_content:

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 ?
---
paper_title: Palindromic Prefixes and Episturmian Words

paper_content:

Let $w$ be an infinite word on an alphabet $A$. We denote by $(n_i)_{i \geq 1}$ the increasing sequence (assumed to be infinite) of all lengths of palindrome prefixes of $w$. In this text, we give an explicit construction of all words $w$ such that $n_{i+1} \leq 2 n_i + 1$ for any $i$, and study these words. Special examples include characteristic Sturmian words, and more generally standard episturmian words. As an application, we study the values taken by the quantity $\limsup n_{i+1}/n_i$, and prove that it is minimal (among all non-periodic words) for the Fibonacci word.
---
paper_title: Palindromic Richness

paper_content:

In this paper, we study combinatorial and structural properties of a new class of finite and infinite words that are 'rich' in palindromes in the utmost sense. A characteristic property of so-called"rich words"is that all complete returns to any palindromic factor are themselves palindromes. These words encompass the well-known episturmian words, originally introduced by the second author together with X. Droubay and G. Pirillo in 2001. Other examples of rich words have appeared in many different contexts. Here we present the first unified approach to the study of this intriguing family of words. Amongst our main results, we give an explicit description of the periodic rich infinite words and show that the recurrent balanced rich infinite words coincide with the balanced episturmian words. We also consider two wider classes of infinite words, namely"weakly rich words"and almost rich words (both strictly contain all rich words, but neither one is contained in the other). In particular, we classify all recurrent balanced weakly rich words. As a consequence, we show that any such word on at least three letters is necessarily episturmian; hence weakly rich words obey Fraenkel's conjecture. Likewise, we prove that a certain class of almost rich words obeys Fraenkel's conjecture by showing that the recurrent balanced ones are episturmian or contain at least two distinct letters with the same frequency. Lastly, we study the action of morphisms on (almost) rich words with particular interest in morphisms that preserve (almost) richness. Such morphisms belong to the class of"P-morphisms"that was introduced by A. Hof, O. Knill, and B. Simon in 1995.
---
paper_title: Episturmian words and some constructions of de Luca and Rauzy

paper_content:

Abstract 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.
---
paper_title: Palindromic complexity of infinite words associated with simple Parry numbers

paper_content:

We study the palindromic complexity of infinite words $u_\beta$, the fixed points of the substitution over a binary alphabet, $\phi(0)=0^a1$, $\phi(1)=0^b1$, with $a-1\geq b\geq 1$, which are canonically associated with quadratic non-simple Parry numbers $\beta$.
---
paper_title: Transcendence measures for continued fractions involving repetitive or symmetric patterns

paper_content:

There is a long tradition in constructing explicit classes of transcendental continued fractions and especially transcendental continued fractions with bounded partial quotients. By means of the Schmidt Subspace Theorem, existing results were recently substantially improved by the authors in a series of papers, providing new classes of transcendental continued fractions. It is the purpose of the present work to show how the Quantitative Subspace Theorem yields transcendence measures for (most of) these numbers.
---
paper_title: A connection between palindromic and factor complexity using return words

paper_content:

In this paper we prove that for any infinite word W whose set of factors is closed under reversal, the following conditions are equivalent: (I) all complete returns to palindromes are palindromes; (II) P(n) + P(n+1) = C(n+1) - C(n) + 2 for all n, where P (resp. C) denotes the palindromic complexity (resp. factor complexity) function of W, which counts the number of distinct palindromic factors (resp. factors) of each length in W.
---
paper_title: Powers in a class of A-strict standard episturmian words

paper_content:

This paper concerns a specific class of strict standard episturmian words whose directive words resemble those of characteristic Sturmian words. In particular, we explicitly determine all integer powers occurring in such infinite words, extending recent results of Damanik and Lenz [D. Damanik, D. Lenz, Powers in Sturmian sequences, European J. Combin. 24 (2003) 377-390, doi:10.1016/S0195-6698(03)00026-X], who studied powers in Sturmian words. The key tools in our analysis are canonical decompositions and a generalization of singular words, which were originally defined for the ubiquitous Fibonacci word. Our main results are demonstrated via some examples, including the k-bonacci word, a generalization of the Fibonacci word to a k-letter alphabet (k>=2).
---
paper_title: A generalization of Sturmian sequences; combinatorial structure and transcendence

paper_content:

We investigate a class of minimal sequences on a finite alphabet Ak = {1,2,...,k} having (k - 1)n + 1 distinct subwords of length n. These sequences, originally defined by P. Arnoux and G. Rauzy, are a natural generalization of binary Sturmian sequences. We describe two simple combinatorial algorithms for constructing characteristic Arnoux-Rauzy sequences (one of which is new even in the Sturmian case). Arnoux-Rauzy sequences arising from fixed points of primitive morphisms are characterized by an underlying periodic structure. We show that every Arnoux-Rauzy sequence contains arbitrarily large subwords of the form V^2+e and, in the Sturmian case, arbitrarily large subwords of the form V^3+e. Finally, we prove that an irrational number whose base b-digit expansion is an Arnoux-Rauzy sequence is transcendental.
---
paper_title: Initial powers of Sturmian sequences

paper_content:

In this paper we investigate powers of prefixes of Sturmian sequences. We give an explicit formula for ice(ω), the initial critical exponent of a Sturmian sequence ω, defined as the supremum of all real numbers p > 0 for which there exist arbitrary long prefixes of ω of the form up, in terms of its S-adic representation. This formula is based on Ostrowski's numeration system. Furthermore we characterize those irrational slopes α of which there exists a Sturmian sequence ω beginning in only finitely many powers of 2 + e, that is for which ice(ω) = 2. In the process we recover the known results for the index (or critical exponent) of a Sturmian sequence. We also focus on the Fibonacci Sturmian shift and prove that the set of Sturmian sequences with ice strictly smaller than its everywhere value has Hausdorff dimension 1.
---
paper_title: Sturmian words and words with a critical exponent

paper_content:

Let S be a standard Sturmian word that is a fixed point of a non-trivial homomorphism. Associated to the infinite word S is a unique irrational number β with 0 0 it contains a fractional power with exponent greater than Ω−e; here Ω is a constant that depends on β. The constant Ω is given explicitly. Using these results we are able to give a short proof of Mignosi's theorem and give an exact evaluation of the maximal power that can occur in a standard Sturmian word.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Transcendence of Numbers with a Low Complexity Expansion

paper_content:

Abstract A sequence is Sturmian if it has complexity n + l −1, that is, n + l −1 factors of length n for every n ; we show that real numbers whose expansion in some base k ⩾ l is Sturmian are transcendental, and give explicit expressions for these numbers. We then generalize the transcendence property to other sequences of low complexity, particularly the Arnoux–Rauzy sequences.
---
paper_title: Some properties of the Tribonacci sequence

paper_content:

In this paper, we consider the factor properties of the Tribonacci sequence. We define the singular words, and then give the singular factorization and the Lyndon factorization. As applications, we study the powers of the factors and the overlap of the factors. We also calculate the free index of the sequence.
---
paper_title: Fractional powers in Sturmian words

paper_content:

Abstract Given an infinite Sturmian word s , we calculate the function L(m) which gives the length of the longest factor of s having period m . The expression of L(m) makes use of the continued fraction of the irrational α associated with s .
---
paper_title: Transcendence of Sturmian or morphic continued fractions

paper_content:

Abstract We prove, using a theorem of W. Schmidt, that if the sequence of partial quotients of the continued fraction expansion of a positive irrational real number takes only two values, and begins with arbitrary long blocks which are “almost squares,” then this number is either quadratic or transcendental. This result applies in particular to real numbers whose partial quotients form a Sturmian (or quasi-Sturmian) sequence, or are given by the sequence (1+(⌊ nα ⌋ mod 2)) n ⩾0 , or are a “repetitive” fixed point of a binary morphism satisfying some technical conditions.
---
paper_title: On the Index of Sturmian Words

paper_content:

An infinite word x has finite index if the exponents of the powers of primitive words that are factors of x are bounded. F. Mignosi has proved that a Sturmian word has finite index if and only if the coefficients of the continued fraction development of its slope are bounded. Mignosi’s proof relies on a delicate analysis of the approximation of the slope by rational numbers. We give here a proof based on combinatorial properties of words, and give some additional relations between the exponents and the slope.
---
paper_title: Frequencies of factors in Arnoux-Rauzy sequences

paper_content:

V. Berthe showed that the frequencies of factors in a Sturmian word of slope α, as well as the number of factors with a given frequency, can be expressed in terms of the continued fraction expansion of α. In this paper we describe a multi-dimensional continued fraction process associated with a class of sequences of (block) complexity kn+1 originally introduced by P. Arnoux and G. Rauzy. This vectorial division algorithm yields simultaneous rational approximations of the frequencies of the letters. We extend Berthe’s result to factors of Arnoux-Rauzy sequences by expressing both the frequencies and the number of factors with a given frequency, in terms of the ‘convergents’ obtained from the generalized continued fraction expansion of the frequencies of the letters.
---
paper_title: A generalization of Sturmian sequences; combinatorial structure and transcendence

paper_content:

We investigate a class of minimal sequences on a finite alphabet Ak = {1,2,...,k} having (k - 1)n + 1 distinct subwords of length n. These sequences, originally defined by P. Arnoux and G. Rauzy, are a natural generalization of binary Sturmian sequences. We describe two simple combinatorial algorithms for constructing characteristic Arnoux-Rauzy sequences (one of which is new even in the Sturmian case). Arnoux-Rauzy sequences arising from fixed points of primitive morphisms are characterized by an underlying periodic structure. We show that every Arnoux-Rauzy sequence contains arbitrarily large subwords of the form V^2+e and, in the Sturmian case, arbitrarily large subwords of the form V^3+e. Finally, we prove that an irrational number whose base b-digit expansion is an Arnoux-Rauzy sequence is transcendental.
---
paper_title: Episturmian words and episturmian morphisms

paper_content:

Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
---
paper_title: Descendants of Primitive Substitutions

paper_content:

Let s = (A, τ) be a primitive substitution. To each decomposition of the form τ (h) = uhv we associate a primitive substitution D [(h,u)] (s) defined on the set of return words to h . The substitution D [(h,u)] (s) is called a descendant of s and its associated dynamical system is the induced system (X h , T h ) on the cylinder determined by h . We show that \( {\cal D}(s) \) , the set of all descendants of s , is finite for each primitive substitution s . We consider this to be a symbolic counterpart to a theorem of Boshernitzan and Carroll which states that an interval exchange transformation defined over a quadratic field has only finitely many descendants. If s fixes a nonperiodic sequence, then \( {\cal D}(s) \) contains a recognizable substitution. Under certain conditions the set \( \Omega (s) = \bigcap_{s^\prime \in {\cal D}(s)}{\cal D}(s^\prime ) \) is nonempty.
---
paper_title: A characterization of Sturmian morphisms

paper_content:

A morphism is called Sturmian if it preserves all Sturmian (infinite) words. It is weakly Sturmian if it preserves at least one Sturmian word. We prove that a morphism is Sturmian if and only if it keeps the word ba2ba2baba2bab balanced. As a consequence, weakly Sturmian morphisms are Sturmian. An application to infinite words associated to irrational numbers is given.
---
paper_title: Substitution dynamical systems : Algebraic characterization of eigenvalues

paper_content:

We give a necessary and sufficient condition allowing to compute explicitly the eigenvalues of the dynamical system associated to any
---
paper_title: A remark on morphic sturmian words

paper_content:

This Note deals with binary Sturmian words that are morphic, i.e. generated by iterating a morphism. Among these, characteristic words are a well-known subclass. We prove that for every characteristic morphic word x, the four words ax, bx, abx and bax are morphic
---
paper_title: Morse and Hedlund’s Skew Sturmian Words Revisited

paper_content:

For any infinite word r over A = {a, b} we associate two infinite words min(r), max(r) such that any prefix of min(r) (max(r), respectively) is the lexicographically smallest (greatest, respectively) among the factors of r of the same length. We prove that (min(r); max(r)) = (as, bs) for some infinite word s if and only if r is a proper Sturmian word or an ultimately periodic word of a particular form. This result is based on a lemma concerning sequences of infinite words.
---
paper_title: On complementary triples of Sturmian bisequences

paper_content:

Abstract A Sturmian bisequence S is a subset of ℤ such that the numbers of elements of S in any two intervals of equal lengths differ by at most 1. A complementary triple of bisequences is a set of three bisequences such that every integer belongs to exactly one bisequence. In the paper a question of Loeve is answered by giving a characterization of all complementary triples of Sturmian bisequences.
---
paper_title: STRUCTURE OF THREE INTERVAL EXCHANGE TRANSFORMATIONS I : AN ARITHMETIC STUDY

paper_content:

Dans cet article nous decrivons une generalisation a la dimension 2 de l'algorithme d'Euclide, qui provient de la dynamique des echanges de 3 intervalles. Nous examinons diverses proprietes diophantiennes de cet algorithme, en particulier la, qualite de l'approximation simultanee. Nous montrons qu'il verifie un theoreme de type Lagrange : l'algorithme est finalement periodique si et seulement si les parametres sont dans la meme extension quadratique de Q.
---
paper_title: Characterizations of finite and infinite episturmian words via lexicographic orderings

paper_content:

In this talk, I will present some new results arising from collaborative work with Jacques Justin (France) and Giuseppe Pirillo (Italy). This work, which extends previous results on extremal properties of infinite Sturmian and episturmian words, is purely combinatorial in nature. Specifically, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.
---
paper_title: Characterizations of finite and infinite episturmian words via lexicographic orderings

paper_content:

In this talk, I will present some new results arising from collaborative work with Jacques Justin (France) and Giuseppe Pirillo (Italy). This work, which extends previous results on extremal properties of infinite Sturmian and episturmian words, is purely combinatorial in nature. Specifically, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.
---
paper_title: Quasiperiodic and Lyndon episturmian words

paper_content:

Recently the second two authors characterized quasiperiodic Sturmian words, proving that a Sturmian word is non-quasiperiodic if and only if, it is an infinite Lyndon word. Here we extend this study to episturmian words (a natural generalization of Sturmian words) by describing all the quasiperiods of an episturmian word, which yields a characterization of quasiperiodic episturmian words in terms of their directive words. Even further, we establish a complete characterization of all episturmian words that are Lyndon words. Our main results show that, unlike the Sturmian case, there is a much wider class of episturmian words that are non-quasiperiodic, besides those that are infinite Lyndon words. Our key tools are morphisms and directive words, in particular normalized directive words, which we introduced in an earlier paper. Also of importance is the use of return words to characterize quasiperiodic episturmian words, since such a method could be useful in other contexts.
---
paper_title: Extremal properties of (epi)Sturmian sequences and distribution modulo 1

paper_content:

Starting from a study of Y. Bugeaud and A. Dubickas (2005) on a question in distribution of real numbers modulo 1 via combinatorics on words, we survey some combinatorial properties of (epi)Sturmian sequences and distribution modulo 1 in connection to their work. In particular we focus on extremal properties of (epi)Sturmian sequences, some of which have been rediscovered several times.
---
paper_title: Symbolic dynamics and rotation numbers

paper_content:

In the space of binary sequences, minimal sets, that is: sets invariant under the shift operation, that have no invariant proper subsets, are investigated. In applications, such as a piecewise linear circle map and the Smale horseshoe in a mapping of the annulus, each of these sets is invariant under the mapping. These sets can be assigned a unique rotation number equal to the average of the number of ones in the sequences.
---
paper_title: Symbolic dynamics of order-preserving orbits

paper_content:

Abstract The maps we consider are roughly those that can be obtained by truncating non-invertible maps to weakly monotonic maps (they have a flat piece). The binary sequences that correspond to order-preserving orbits are shown to satisfy a minimax principle (which was already known for order-preserving orbits with rational rotation number). The converse is also proven: all minimax orbits are order-preserving with respect to some rotation number. For certain families of such circle maps one can solve exactly for the parameter values for which the map has a specified rotation number rho. For rho rational we obtain the endpoints of the resonance intervals recursively. These parameter values can be organized in a natural way as the nodes of a Farey tree. We give some applications of the ideas discussed.
---
paper_title: Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words

paper_content:

Using the notions of conjugacy of morphisms and of morphisms preserving Lyndon words, we answer a question of G. Melancon. We characterize cases where the sequence of Lyndon words in the Lyndon factorization of a standard Sturmian word is morphic. In each possible case, the corresponding morphism is given.
---
paper_title: Inequalities characterizing standard Sturmian and episturmian words

paper_content:

Considering the smallest and the greatest factors with respect to the lexicographic order we associate to each infinite word r two other infinite words min(r) and max(r). In this paper we prove that the inequalities as ≤ min(s) ≤ max(s) ≤ bs characterize standard Sturmian words (proper ones and periodic ones) and that the condition "for any x ∈ A and lexicographic order < satisfying x = min(A) one has xs ≤ min(s)" characterizes standard episturmian words.
---
paper_title: Quasiperiodic Sturmian words and morphisms

paper_content:

We characterize all quasiperiodic Sturmian words: a Sturmian word is not quasiperiodic if and only if it is a Lyndon word. Moreover, we study links between Sturmian morphisms and quasiperiodicity.
---
paper_title: On a characteristic property of ARNOUX–RAUZY sequences

paper_content:

Here we give a characterization of Arnoux-Rauzy sequences by the way of the lexicographic orderings of their alphabet.
---
paper_title: Characterizations of finite and infinite episturmian words via lexicographic orderings

paper_content:

In this talk, I will present some new results arising from collaborative work with Jacques Justin (France) and Giuseppe Pirillo (Italy). This work, which extends previous results on extremal properties of infinite Sturmian and episturmian words, is purely combinatorial in nature. Specifically, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.
---
paper_title: A local balance property of episturmian words

paper_content:

We prove that episturmian words and Arnoux-Rauzy sequences can be characterized using a local balance property. We also give a new characterization of epistandard words.
---
paper_title: A generalization of Sturmian sequences; combinatorial structure and transcendence

paper_content:

We investigate a class of minimal sequences on a finite alphabet Ak = {1,2,...,k} having (k - 1)n + 1 distinct subwords of length n. These sequences, originally defined by P. Arnoux and G. Rauzy, are a natural generalization of binary Sturmian sequences. We describe two simple combinatorial algorithms for constructing characteristic Arnoux-Rauzy sequences (one of which is new even in the Sturmian case). Arnoux-Rauzy sequences arising from fixed points of primitive morphisms are characterized by an underlying periodic structure. We show that every Arnoux-Rauzy sequence contains arbitrarily large subwords of the form V^2+e and, in the Sturmian case, arbitrarily large subwords of the form V^3+e. Finally, we prove that an irrational number whose base b-digit expansion is an Arnoux-Rauzy sequence is transcendental.
---
paper_title: Complementing and exactly covering sequences

paper_content:

Abstract The following is proved (in a slightly more general setting): Let α1, …, αm be positive real, γ1, …, γm real, and suppose that the system [nαi + γi], i = 1, …, m, n = 1, 2, …, contains every positive integer exactly once (= a complementing system). Then α i α j is an integer for some i ≠ j in each of the following cases: (i) m = 3 and m = 4; (ii) m = 5 if all αi but one are integers; (iii) m ⩾ 5, two of the αi are integers, at least one of them prime; (iv) m ⩾ 5 and αn ⩽ 2n for n = 1, 2, …, m − 4. For proving (iv), a method of reduction is developed which, given a complementing system of m sequences, leads under certain conditions to a derived complementing system of m − 1 sequences.
---
paper_title: Fraenkel's conjecture for six sequences

paper_content:

Abstract A striking conjecture of Fraenkel asserts that every decomposition of Z >0 into m ⩾3 sets {⌊α i n+β i ⌋} n∈ Z >0 with α i and β i real, α i >1 and α i 's distinct for i =1,…, m satisfies {α 1 ,…,α m }= 2 m −1 2 k : 0⩽k . Fraenkel's conjecture was proved by Morikawa if m =3 and, under some condition, if m =4. Proofs in terms of balanced sequences have been given for m =3 by the author and for m =4 by Altman, Gaujal and Hordijk. In the present paper we use the latter approach to establish Fraenkel's conjecture for m =5 and for m =6.
---
paper_title: A Characterization of Balanced Episturmian Sequences

paper_content:

It is well known that Sturmian sequences are the aperiodic sequences that are balanced over a 2-letter alphabet. They are also characterized by their complexity: they have exactly $(n+1)$ factors of length $n$. One possible generalization of Sturmian sequences is the set of infinite sequences over a $k$-letter alphabet, $k \geq 3$, which are closed under reversal and have at most one right special factor for each length. This is the set of episturmian sequences. These are not necessarily balanced over a $k$-letter alphabet, nor are they necessarily aperiodic. In this paper, we characterize balanced episturmian sequences, periodic or not, and prove Fraenkel's conjecture for the class of episturmian sequences. This conjecture was first introduced in number theory and has remained unsolved for more than 30 years. It states that for a fixed $k> 2$, there is only one way to cover $\Z$ by $k$ Beatty sequences. The problem can be translated to combinatorics on words: for a $k$-letter alphabet, there exists only one balanced sequence up to letter permutation that has different letter frequencies.
---
paper_title: Quasiperiodic and Lyndon episturmian words

paper_content:

Recently the second two authors characterized quasiperiodic Sturmian words, proving that a Sturmian word is non-quasiperiodic if and only if, it is an infinite Lyndon word. Here we extend this study to episturmian words (a natural generalization of Sturmian words) by describing all the quasiperiods of an episturmian word, which yields a characterization of quasiperiodic episturmian words in terms of their directive words. Even further, we establish a complete characterization of all episturmian words that are Lyndon words. Our main results show that, unlike the Sturmian case, there is a much wider class of episturmian words that are non-quasiperiodic, besides those that are infinite Lyndon words. Our key tools are morphisms and directive words, in particular normalized directive words, which we introduced in an earlier paper. Also of importance is the use of return words to characterize quasiperiodic episturmian words, since such a method could be useful in other contexts.
---
paper_title: On stabilizers of infinite words

paper_content:

The stabilizer of an infinite word w over a finite alphabet @S is the monoid of morphisms over @S that fix w. In this paper we study various problems related to stabilizers and their generators. We show that over a binary alphabet, there exist stabilizers with at least n generators for all n. Over a ternary alphabet, the monoid of morphisms generating a given infinite word by iteration can be infinitely generated, even when the word is generated by iterating an invertible primitive morphism. Stabilizers of strict epistandard words are cyclic when non-trivial, while stabilizers of ultimately strict epistandard words are always non-trivial. For this latter family of words, we give a characterization of stabilizer elements.
---
paper_title: Efficient detection of quasiperiodicities in strings

paper_content:

A string z is quasiperiodic if there is a second string w ≠ z such that the occurrences of w in z cover z entirely, i.e., every position of z falls within some occurrence of w in z. It is shown here that all maximal quasiperiodic substrings of a string x of n symbols can be detected in time O(n log2 n).
---
paper_title: Quasiperiodic infinite words : multi-scale case and dynamical properties

paper_content:

An infinite word x is said to be quasiperiodic if there exists a finite word q such that x is covered by occurrences of q (such a q is called a quasiperiod of x). Using the notion of derivation, we show that this definition is not sufficient to imply any symmetry in an infinite word. Therefore we introduce multi-scale quasiperiodic words, i.e. quasiperiodic words that admit an infinite number of quasiperiods. Such words are uniformly recurrent, this allows us to study the subshift they generate. We prove that multi-scale quasiperiodic subshifts are uniquely ergodic and have zero topological entropy as well as zero Kolmogorov complexity. Sturmian subshifts are shown to be multi-scale quasiperiodic.
---
paper_title: On different generalizations of episturmian words

paper_content:

In this paper we study some classes of infinite words generalizing episturmian words, and analyse the relations occurring among such classes. In each case, the reversal operator R is replaced by an arbitrary involutory antimorphism @q of the free monoid A^*. In particular, we define the class of @q-words with seed, whose ''standard'' elements (@q-standard words with seed) are constructed by an iterative @q-palindrome closure process, starting from a finite word u"0 called the seed. When the seed is empty, one obtains @q-words; episturmian words are exactly the R-words. One of the main theorems of the paper characterizes @q-words with seed as infinite words closed under @q and having at most one left special factor of each length n>=N (where N is some nonnegative integer depending on the word). When N=0 we call such words @q-episturmian. Further results on the structure of @q-episturmian words are proved. In particular, some relationships between @q-words (with or without seed) and @q-episturmian words are shown.
---
paper_title: Quasiperiodic Sturmian words and morphisms

paper_content:

We characterize all quasiperiodic Sturmian words: a Sturmian word is not quasiperiodic if and only if it is a Lyndon word. Moreover, we study links between Sturmian morphisms and quasiperiodicity.
---
paper_title: On some problems related to palindrome closure

paper_content:

In this paper, we solve some open problems related to (pseudo)palindrome closure operators and to the infinite words generated by their iteration, that is, standard episturmian and pseudostandard words. We show that if ϑ is an involutory antimorphism of A* , then the right and left ϑ -palindromic closures of any factor of a ϑ -standard word are also factors of some ϑ -standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure starting from a nonempty word. We show that pseudostandard words with seed are morphic images of standard episturmian words. Moreover, we prove that for any given pseudostandard word s with seed, all sufficiently long left special factors of s are prefixes of it.
---
paper_title: String Pattern Matching for a Deluge Survival Kit

paper_content:

String Pattern Matching concerns itself with algorithmic and combinatorial issues related to matching and searching on linearly arranged sequences of symbols, arguably the simplest possible discrete structures. As unprecedented volumes of sequence data are amassed, disseminated and shared at an increasing pace, effective access to, and manipulation of such data depend crucially on the efficiency with which strings are structured, compressed, transmitted, stored, searched and retrieved. This paper samples from this perspective, and with the authors' own bias, a rich arsenal of ideas and techniques developed in more than three decades of history.
---

Title: Episturmian Words: A Survey

Section 1: From Sturmian to episturmian
Description 1: This section introduces the concept of Sturmian words and their fascinating properties, leading to the natural extension to episturmian words.

Section 2: Notation & terminology
Description 2: This section provides definitions, notations, and terminologies related to episturmian words, essential for understanding the subsequent sections.

Section 3: Definitions & basic properties
Description 3: This section offers the foundational definitions and basic properties of episturmian words, including their characteristic attributes and generalizations.

Section 4: Equivalence classes
Description 4: This section explores the classification of infinite words into equivalence classes based on their factor sets, particularly focusing on episturmian words.

Section 5: Bi-infinite episturmian words
Description 5: This section extends the concept of episturmian words to bi-infinite words and discusses their recurrence properties and related formulations.

Section 6: Strict episturmian words
Description 6: This section defines strict episturmian words and discusses their properties in terms of their alphabets and special factors.

Section 7: Episturmian morphisms
Description 7: This section introduces episturmian morphisms, their significance, and how they generalize Sturmian morphisms to larger alphabets.

Section 8: Generators & monoids
Description 8: This section details the generators and monoids of episturmian morphisms, demonstrating various inclusions and decompositions.

Section 9: Relation with episturmian words
Description 9: This section characterizes episturmian words using their decompositions over pure episturmian morphisms and directive words.

Section 10: Spins, shifts, and directive words
Description 10: This section examines the concepts of spins, shifts, and directive words, illustrating how these notions impact the structure of episturmian words.

Section 11: Notation for pure episturmian morphisms
Description 11: This section introduces a notation system for pure episturmian morphisms and discusses their operational principles.

Section 12: Shifts
Description 12: This section explores the impact of shifts on episturmian morphisms and how they relate to conjugate morphisms.

Section 13: Block-equivalence & directive words
Description 13: This section discusses block-equivalence for spinned words and their influence on representing episturmian words.

Section 14: Periodic and purely morphic episturmian words
Description 14: This section describes periodic and purely morphic episturmian words in terms of their directive words and morphic structures.

Section 15: Arnoux-Rauzy sequences
Description 15: This section briefly discusses Arnoux-Rauzy sequences and their combinatorial properties, elucidating their relation to episturmian words.

Section 16: Finite Arnoux-Rauzy words
Description 16: This section considers finite episturmian words and their enumeration and characterization with respect to their periodic properties.

Section 17: Some properties of factors
Description 17: This section summarizes various properties of factors of episturmian words including factor complexity, palindromes, and more.

Section 18: Factor complexity
Description 18: This section provides detailed insights into the complexity of factors in episturmian words.

Section 19: Palindromic factors
Description 19: This section discusses the palindromic factors in episturmian words and their implications.

Section 20: Iterated palindromic closure
Description 20: This section elaborates on the process and significance of iterated palindromic closure in the context of episturmian words.

Section 21: Palindromic richness
Description 21: This section defines and explores the concept of palindromic richness within episturmian words.

Section 22: Fractional powers & critical exponent
Description 22: This section investigates the occurrence of fractional powers in episturmian words and the concepts of the critical exponent.

Section 23: Frequencies
Description 23: This section discusses the frequency of factors within episturmian words, providing formulas and examples.

Section 24: Return words
Description 24: This section introduces the notion of return words and their significance in the study of episturmian words.

Section 25: Episkew words
Description 25: This section defines episkew words and discusses their equivalence to episturmian words and their properties.

Section 26: Extremal properties
Description 26: This section explores the extremal properties of episturmian words with respect to lexicographic order.

Section 27: Imbalance
Description 27: This section discusses the balance properties of episturmian words and how they relate to episturmian sequences.

Section 28: Fraenkel's conjecture
Description 28: This section addresses Fraenkel's conjecture in the context of balanced episturmian words and recurrent sequences.

Section 29: Concluding remarks
Description 29: This section concludes the survey by mentioning recent research works and open questions involving episturmian words.