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 and Lyndon episturmian words

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.     

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 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 the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters

We give lower bounds on the growth rate of Dejean words, i.e. minimally repetitive words, over a k-letter alphabet, for 5≤k≤10. Put together with the known upper bounds, we estimate these growth rates with the precision of 0.005. As a consequence, we establish the exponential growth of the number of Dejean words over a k-letter alphabet, for 5≤k≤10.     

Unavoidable Sets of Partial Words

The notion of an unavoidable set of words appears frequently in the fields of mathematics and theoretical computer science, in particular with its connection to the study of combinatorics on words. The theory of unavoidable sets has seen extensive study over the past twenty years. In this paper we extend the definition of unavoidable sets of words to unavoidable sets of partial words. Partial words, or finite sequences that may contain a number of “do not know” symbols or “holes,” appear naturally in several areas of current interest such as molecular biology, data communication, and DNA computing. We demonstrate the utility of the notion of unavoidability of sets of partial words by making use of it to identify several new classes of unavoidable sets of full words. Along the way we begin work on classifying the unavoidable sets of partial words of small cardinality. We pose a conjecture, and show that affirmative proof of this conjecture gives a sufficient condition for classifying all the unavoidable sets of partial words of size two. We give a result which makes the conjecture easy to verify for a significant number of cases. We characterize many forms of unavoidable sets of partial words of size three over a binary alphabet, and completely characterize such sets over a ternary alphabet. Finally, we extend our results to unavoidable sets of partial words of size k over a k-letter alphabet. This material is based upon work supported by the National Science Foundation under Grant No. DMS-0452020. Part of this paper was presented at DLT’07 [4]. We thank the referees as well as Robert Mercaş and Geoffrey Scott for very valuable comments and suggestions. World Wide Web server interfaces have been established at and for automated use of the programs.     

Minimal non-convex words

Using a combinatorial characterization of digital convexity based on words, one defines the language of convex words. The complement of this language forms an ideal whose minimal elements, with respect to the factorial ordering, appear to have a particular combinatorial structure very close to the Christoffel words. In this paper, those words are completely characterized as those of the form uw^kv where k≥1, w=u⋅v and u,v,w are Christoffel words. Also, by considering the most balanced among the unbalanced words, we obtain a second characterization for a special class of minimal non-convex words that are of the form u²v² corresponding to the case k=1 in the previous form.     

A strongly primitive word of arbitrary length and its application †

It is known that both the class of all (n,k)-languages and the class of all time-variant languages over a finite alphabet contain the class of all regular languages. In this paper we show that in general neither one of these two classes of languages contains the other by constructing an infinite sequence of strongly primitive words over an alphabet with four letters.     

On stabilizers of infinite words

The stabilizer of an infinite word over a finite alphabet Σ is the monoid of morphisms over Σ that fix . 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.     

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.     

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.     

A generalization of Thue freeness for partial words

This paper approaches the combinatorial problem of Thue freeness for partial words. Partial words are sequences over a finite alphabet that may contain a number of “holes”. First, we give an infinite word over a three-letter alphabet which avoids squares of length greater than two even after we replace an infinite number of positions with holes. Then, we give an infinite word over an eight-letter alphabet that avoids longer squares even after an arbitrary selection of its positions are replaced with holes, and show that the alphabet size is optimal. We find similar results for overlap-free partial words.     

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     

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.     

A Sturmian sequence related to the uniqueness conjecture for Markoff numbers

Sturmian sequences appear in the work of Markoff on approximations of real numbers and minima of quadratic functions. In particular, Christoffel words, or equivalently pairs of relatively prime nonnegative integers, parametrize the Markoff numbers. It was asked by Frobenius if this parametrization is injective. We answer this conjecture for a particular subclass of these numbers, and show that a special Sturmian sequence of irrational slope determines the order of the Markoff numbers in this subclass.     

Exponential lower bounds for the number of words of uniform length avoiding a pattern

We study words on a finite alphabet avoiding a finite collection of patterns. Given a pattern p in which every letter that occurs in p occurs at least twice, we show that the number of words of length n on a finite alphabet that avoid p grows exponentially with n as long as the alphabet has at least four letters. Moreover, we give lower bounds describing this exponential growth in terms of the size of the alphabet and the number of letters occurring in p. We also obtain analogous results for the number of words avoiding a finite collection of patterns. We conclude by giving some questions.     

Topology on words

We investigate properties of topologies on sets of finite and infinite words over a finite alphabet. The guiding example is the topology generated by the prefix relation on the set of finite words, considered as a partial order. This partial order extends naturally to the set of infinite words; hence it generates a topology on the union of the sets of finite and infinite words. We consider several partial orders which have similar properties and identify general principles according to which the transition from finite to infinite words is natural. We provide a uniform topological framework for the set of finite and infinite words to handle limits in a general fashion.     

The syntactic monoid of hairpin-free languages

The study of hairpin-free words has been initiated in the context of DNA computing. DNA strands that, theoretically speaking, are finite strings over the alphabet {A, G, C, T} are used in DNA computing to encode information. Due to the fact that A is complementary to T and G to C, DNA single strands that are complementary can bind to each other or to themselves in either intended or unintended ways. One of the structures that is usually undesirable for biocomputation, since it makes the affected DNA string unavailable for future interactions, is the hairpin: if some subsequences of a DNA single string are complementary to each other, the string will bind to itself forming a hairpin-like structure. This paper continues the theoretical study of hairpin-free languages. We study algebraic properties of hairpin-free words and hairpins. We also give a complete characterization of the syntactic monoid of the language consisting of all hairpin-free words over a given alphabet and illustrate it with an example using the DNA alphabet.     

Special sequences as subcodes of reed-solomon codes

We consider sequences in which every symbol of an alphabet occurs at most once. We construct families of such sequences as nonlinear subcodes of a q-ary [n, k, n − k + 1] _q Reed-Solomon code of length n ≤ q consisting of words that have no identical symbols. We introduce the notion of a bunch of words of a linear code. For dimensions k ≤ 3 we obtain constructive lower estimates (tight bounds in a number of cases) on the maximum cardinality of a subcode for various n and q, and construct subsets of words meeting these estimates and bounds. We define codes with words that have no identical symbols, observe their relation to permutation codes, and state an optimization problem for them.