Now showing items 11-20 of 27
Unary patterns under permutations
Thue characterized completely the avoidability of unary patterns. Adding function variables gives a general setting capturing avoidance of powers, avoidance of patterns with palindromes, avoidance of powers under coding, ...
Growth rate of binary words avoiding xxxR
Abstract Consider the set of those binary words with no non-empty factors of the form xxx^R. Du, Mousavi, Schaeffer, and Shallit asked whether this set of words grows polynomially or exponentially with length. In this ...
For each a > 2 there is an Infinite Binary Word with Critical Exponent a
(The Electronic Journal of Combinatorics, 2008-08-31)
The critical exponent of an infinite word w is the supremum of all rational numbers α such that w contains an α-power. We resolve an open question of Krieger and Shallit by showing that for each α>2 there is an infinite ...
Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101
We characterize exactly the lengths of binary circular words containing no squares other than 00, 11, and 0101.
There are Ternary Circular Square-Free Words of Length n for n ≥ 18
(The Electronic Journal of Combinatorics, 2002-10-11)
There are circular square-free words of length n on three symbols for n≥18. This proves a conjecture of R. J. Simpson.
On avoidability of formulas with reversal
(EDP Sciences, 2018-02-13)
While a characterization of unavoidable formulas (without reversal) is well-known, little is known about the avoidability of formulas with reversal in general. In this article, we characterize the unavoidable formulas ...
Square-free Words with Square-free Self-shuffles
(The Electronic Journal of Combinatorics, 2014-01-12)
We answer a question of Harju: For every n ≥ 3 there is a square-free ternary word of length n with a square-free self-shuffle.
Binary Words Avoiding xxRx and Strongly Unimodal Sequences
In previous work, Currie and Rampersad showed that the growth of the number of binary words avoiding the pattern xxxR was intermediate between polynomial and exponential. We now show that the same result holds for the ...
Extremal words in morphic subshifts
Given an infinite word x over an alphabet A, a letter b occurring in x, and a total order \sigma on A, we call the smallest word with respect to \sigma starting with b in the shift orbit closure of x an extremal word of ...
Attainable lengths for circular binary words avoiding k-powers
(The Belgian Mathematical Society, 2005)
We show that binary circular words of length n avoiding 7/3+ powers exist for every sufficiently large n. This is not the case for binary circular words avoiding k+ powers with k < 7/3