A note on a conjecture of Duval and sturmian words
We prove a long standing conjecture of Duval in the special case of sturmian words.
A Note on a Conjecture of Duval and Sturmian Words
We prove a long standing conjecture of Duval in the special case of Sturmian words.
A note on antichains of words.
A note on constructing infinite binary words with polynomial subword complexity
Most of the constructions of infinite words having polynomial subword complexity are quite complicated, e.g., sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words w over a binary alphabet { a,b } with polynomial subword complexity pw. Assuming w contains an infinite number of a’s, our method is based on the gap function which gives the distances between consecutive b’s. It is known that if the gap function...
A note on the number of squares in a partial word with one hole
A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length n is bounded by 2n since at each position there are at most two distinct squares whose last occurrence starts. In this paper, we investigate squares in partial words with one hole, or sequences over a finite alphabet that have a “do not know” symbol or “hole”. A square in a partial word over a given alphabet has the form uv where u is compatible with v, and consequently, such square is...
A note on univoque self-sturmian numbers
We compare two sets of (infinite) binary sequences whose suffixes satisfy extremal conditions: one occurs when studying iterations of unimodal continuous maps from the unit interval into itself, but it also characterizes univoque real numbers; the other is a disguised version of the set of characteristic sturmian sequences. As a corollary to our study we obtain that a real number in is univoque and self-sturmian if and only if the -expansion of is of the form , where is a characteristic...
A note on univoque self-Sturmian numbers
We compare two sets of (infinite) binary sequences whose suffixes satisfy extremal conditions: one occurs when studying iterations of unimodal continuous maps from the unit interval into itself, but it also characterizes univoque real numbers; the other is a disguised version of the set of characteristic Sturmian sequences. As a corollary to our study we obtain that a real number β in (1,2) is univoque and self-Sturmian if and only if the β-expansion of 1 is of the form 1v, where v is a characteristic...
A one-sided Zimin construction.
A periodicity property of iterated morphisms
Suppose ƒ : X* → X* is a morphism and u,v ∈ X*. For every nonnegative integer n, let zn be the longest common prefix of ƒn(u) and ƒn(v), and let un,vn ∈ X* be words such that ƒn(u) = znun and ƒn(v) = znvn. We prove that there is a positive integer q such that for any positive integer p, the prefixes of un (resp. vn) of length p form an ultimately periodic sequence having period q. Further, there is a value of q which works for all words u,v ∈ X*.
A remark on morphic sturmian words
A sparse dynamic programming algorithm for alignment with non-overlapping inversions
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is still unknown....
A sparse dynamic programming algorithm for alignment with non-overlapping inversions
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is...
A test-set for -power-free binary morphisms
A morphism is -power-free if and only if is -power-free whenever is a -power-free word. A morphism is -power-free up to if and only if is -power-free whenever is a -power-free word of length at most . Given an integer , we prove that a binary morphism is -power-free if and only if it is -power-free up to . This bound becomes linear for primitive morphisms: a binary primitive morphism is -power-free if and only if it is -power-free up to
A test-set for k-power-free binary morphisms
A morphism f is k-power-free if and only if f(w) is k-power-free whenever w is a k-power-free word. A morphism f is k-power-free up to m if and only if f(w) is k-power-free whenever w is a k-power-free word of length at most m. Given an integer k ≥ 2, we prove that a binary morphism is k-power-free if and only if it is k-power-free up to k2. This bound becomes linear for primitive morphisms: a binary primitive morphism is k-power-free if and only if it is k-power-free up to 2k+1
A theorem of Cobham for non-primitive substitutions
A van der Waerden variant.
Abelian pattern avoidance in partial words
Pattern avoidance is an important topic in combinatorics on words which dates back to the beginning of the twentieth century when Thue constructed an infinite word over a ternary alphabet that avoids squares, i.e., a word with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. On the other hand, Erdős raised the question as to whether there exists an infinite word that avoids abelian squares, i.e.,...
Abelian periods, partial words, and an extension of a theorem of Fine and Wilf
Recently, Constantinescu and Ilie proved a variant of the well-known periodicity theorem of Fine and Wilf in the case of two relatively prime abelian periods and conjectured a result for the case of two non-relatively prime abelian periods. In this paper, we answer some open problems they suggested. We show that their conjecture is false but we give bounds, that depend on the two abelian periods, such that the conjecture is true for all words having length at least those bounds and show that some...
Affinely self-generating sets and morphisms.
An algorithm for deciding if a polyomino tiles the plane
For polyominoes coded by their boundary word, we describe a quadratic O(n2) algorithm in the boundary length n which improves the naive O(n4) algorithm. Techniques used emanate from algorithmics, discrete geometry and combinatorics on words.