Powers in a class of -strict standard episturmian words

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).     

Quasiperiodic Sturmian words and morphisms

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.     

On graphs of central episturmian words

Episturmian sequences are a natural extension of Sturmian sequences to the case of finite alphabets of arbitrary cardinality. In this paper, we are interested in central episturmian words, or simply, epicentral words, i.e., the palindromic prefixes of standard episturmian sequences. An epicentral word admits a variety of faithful representations including as a directive word, as a certain type of period vector, as a Parikh vector, as a certain type of Fine and Wilf extremal word, as a suitable modular matrix, and as a labeled graph. Various interconnections between the different representations of an epicentral word are analyzed. In particular, we investigate the structure of the graphs of epicentral words proving some curious and surprising properties.     

On a generalization of Christoffel words: epichristoffel words

Sturmian sequences are well-known as the ones having minimal complexity over a 2-letter alphabet. They are also the balanced sequences over a 2-letter alphabet and the sequences describing discrete lines. They are famous and have been extensively studied since the 18th century. One of the extensions of these sequences over a k-letter alphabet, with k≥3, is the episturmian sequences, which generalizes a construction of Sturmian sequences using the palindromic closure operation. There exists a finite version of the Sturmian sequences called the Christoffel words. They have been known since the works of Christoffel and have interested many mathematicians. In this paper, we introduce a generalization of Christoffel words for an alphabet with 3 letters or more, using the episturmian morphisms. We call them the epichristoffel words. We define this new class of finite words and show how some of the properties of the Christoffel words can be generalized naturally or not for this class.     

On the structure of bispecial Sturmian words

A balanced word is one in which any two factors of the same length contain the same number of each letter of the alphabet up to one. Finite binary balanced words are called Sturmian words. A Sturmian word is bispecial if it can be extended to the left and to the right with both letters remaining a Sturmian word. There is a deep relation between bispecial Sturmian words and Christoffel words, that are the digital approximations of Euclidean segments in the plane. In 1997, J. Berstel and A. de Luca proved that palindromic bispecial Sturmian words are precisely the maximal internal factors of primitive Christoffel words. We extend this result by showing that bispecial Sturmian words are precisely the maximal internal factors of all Christoffel words. Our characterization allows us to give an enumerative formula for bispecial Sturmian words. We also investigate the minimal forbidden words for the language of Sturmian words.     

On factorially balanced sets of words

A set of words is factorially balanced if the set of all the factors of its words is balanced. We prove that if all words of a factorially balanced set have a finite index, then this set is a subset of the set of factors of a Sturmian word. Moreover, characterizing the set of factors of a given length n of a Sturmian word by the left special factor of length n−1 of this Sturmian word, we provide an enumeration formula for the number of sets of words that correspond to some set of factors of length n of a Sturmian word.     

Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words

Using the notions of conjugacy of morphisms and of morphisms preserving Lyndon words, we answer a question of G. Melançon. 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.     

On the arithmetical complexity of Sturmian words

Using the geometric dual technique by Berstel and Pocchiola, we give a uniform O(n³)$O\left(n^3\right)$ upper bound for the arithmetical complexity of a Sturmian word. We also give explicit expressions for the arithmetical complexity of Sturmian words of slope between 1/3 and 2/3 (in particular, of the Fibonacci word). In this case, the difference between the genuine arithmetical complexity function and our upper bound is bounded, and ultimately 2-periodic. In fact, our formula is valid not only for Sturmian words but for rotation words from a wider class.     

An extension of the Lyndon-Schützenberger result to pseudoperiodic words

One of the particularities of information encoded as DNA strands is that a string u contains basically the same information as its Watson-Crick complement, denoted here as θ(u). Thus, any expression consisting of repetitions of u and θ(u) can be considered in some sense periodic. In this paper, we give a generalization of Lyndon and Schützenberger’s classical result about equations of the form u^l=vⁿw^m, to cases where both sides involve repetitions of words as well as their complements. Our main results show that, for such extended equations, if l?5,n,m?3, then all three words involved can be expressed in terms of a common word t and its complement θ(t). Moreover, if l?5, then n=m=3 is an optimal bound. These results are established based on a complete characterization of all possible overlaps between two expressions that involve only some word u and its complement θ(u), which is also obtained in this paper.     

Special factors,periodicity, and an application to Sturmian words

Let w be a finite word and n the least non-negative integer such that w has no right special factor of length and its right factor of length n is unrepeated. We prove that if all the factors of another word v up to the length n + 1 are also factors of w, thenv itself is a factor ofw. A similar result for ultimately periodic infinite words is established. As a consequence, some ‘uniqueness conditions’ for ultimately periodic words are obtained as well as an upper bound for the rational exponents of the factors of uniformly recurrent non-periodic infinite words. A general formula is derived for the ‘critical exponent’ of a power-free Sturmian word. In particular, we effectively compute the ‘critical exponent’ of any Sturmian sequence whose slope has a periodic development in a continued fraction. Received: 6 May 1999 / 21 February 2000     

Relation between powers of factors and the recurrence function characterizing Sturmian words

In this paper we use the relation of the index of an infinite aperiodic word and its recurrence function to give another characterization of Sturmian words. As a by-product, we give a new proof of the theorem describing the index of a Sturmian word in terms of the continued fraction expansion of its slope. This theorem was independently proved in [A. Carpi, A. de Luca, Special factors, periodicity, and an application to Sturmian words, Acta Inform. 36 (2000) 983–1006] and [D. Damanik, D. Lenz, The index of Sturmian sequences, European J. Combin. 23 (2002) 23–29].     

Periodic and Sturmian languages

Counting the number of distinct factors in the words of a language gives a measure of complexity for that language similar to the factor-complexity of infinite words. Similarly as for infinite words, we prove that this complexity function f(n) is either bounded or f(n)?n+1. We call languages with bounded complexity periodic and languages with complexity f(n)=n+1Sturmian. We describe the structure of periodic languages and characterize the Sturmian languages as the sets of factors of (one- or two-way) infinite Sturmian words.     

Words derivated from Sturmian words

A return word of a factor of a Sturmian word starts at an occurrence of that factor and ends exactly before its next occurrence. Derivated words encode the unique decomposition of a word in terms of return words. Vuillon has proved that each factor of a Sturmian word has exactly two return words. We determine these two return words, as well as their first occurrence, for the prefixes of characteristic Sturmian words. We then characterize words derivated from a characteristic Sturmian word and give their precise form. Finally, we apply our results to obtain a new proof of the characterization of characteristic Sturmian words which are fixed points of morphisms.     

A note on the Markoff condition and central words

We define Markoff words as certain factors appearing in bi-infinite words satisfying the Markoff condition. We prove that these words coincide with central words, yielding a new characterization of Christoffel words.     

Square-free partial words

We say that a partial word w over an alphabet A is square-free if every factor xx^′ of w such that x and x^′ are compatible is either of the form ?a or a? where ? is a hole and a∈A. We prove that there exist uncountably many square-free partial words over a ternary alphabet with an infinite number of holes.     

A new characteristic property of rich words

Originally introduced and studied by the third and fourth authors together with J. Justin and S. Widmer (2008), rich words constitute a new class of finite and infinite words characterized by containing the maximal number of distinct palindromes. Several characterizations of rich words have already been established. A particularly nice characteristic property is that all ‘complete returns’ to palindromes are palindromes. In this note, we prove that rich words are also characterized by the property that each factor is uniquely determined by its longest palindromic prefix and its longest palindromic suffix.     

On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

Avoiding large squares in partial words

Well-known results on the avoidance of large squares in (full) words include the following: (1) Fraenkel and Simpson showed that we can construct an infinite binary word containing at most three distinct squares; (2) Entringer, Jackson and Schatz showed that there exists an infinite binary word avoiding all squares of the form xx such that |x|≥3, and that the bound 3 is optimal; (3) Dekking showed that there exists an infinite cube-free binary word that avoids all squares xx with |x|≥4, and that the bound of 4 is best possible. In this paper, we investigate these avoidance results in the context of partial words, or sequences that may have some undefined symbols called holes. Here, a square has the form uv with u and v compatible, and consequently, such a square is compatible with a number of full words that are squares over the given alphabet. We show that (1) holds for partial words with at most two holes. We prove that (2) extends to partial words having infinitely many holes. Regarding (3), we show that there exist binary partial words with infinitely many holes that avoid cubes and have only eleven full word squares compatible with factors of it. Moreover, this number is optimal, and all such squares xx satisfy |x|≤4.     

Note on powers in three interval exchange transformations

We study repetitions in infinite words coding exchange of three intervals with permutation (3, 2, 1), called 3iet words. The language of such words is determined by two parameters, ε,?. We show that finiteness of the index of 3iet words is equivalent to boundedness of the coefficients of the continued fraction of ε. In this case, we also give an upper and a lower estimate on the index of the corresponding 3iet word. Our main tool is the connection between a 3iet word with parameters ε,? and sturmian words with slope ε.