Search
Now showing items 1-10 of 26
Least Periods of Factors of Infinite Words
(EDP Sciences, 2009)
We show that any positive integer is the least period of a factor of the Thue-Morse word. We also characterize the set of least periods of factors of a Sturmian word. In particular, the corresponding set for the Fibonacci ...
Unary patterns under permutations
(Elsevier, 2018-06-04)
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, ...
Non-Repetitive Tilings
(The Electronic Journal of Combinatorics, 2002-07-03)
In 1906 Axel Thue showed how to construct an infinite non-repetitive (or square-free) word on an alphabet of size 3. Since then this result has been rediscovered many times and extended in many ways. We present a two-dimensional ...
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.
Counting endomorphisms of crown-like orders
(Springer, 2002-12)
The authors introduce the notion of crown-like orders and introduce powerful tools for counting the endomorphisms of orders of this type.
Binary Words Avoiding xxRx and Strongly Unimodal Sequences
(2015-09-14)
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 Infinite Overlap-Free Binary Words
(The Electronic Journal of Combinatorics, 1998-05-03)
Let t be the infinite fixed point, starting with 1, of the morphism μ:0→01, 1→10. An infinite word over {0,1} is said to be overlap-free if it contains no factor of the form axaxa, where a∈{0,1} and x∈{0,1}∗. We prove that ...
Suffix conjugates for a class of morphic subshifts
(Cambridge University Press, 2015-09)
Let A be a finite alphabet and f: A^* --> A^* be a morphism with an iterative fixed point f^\omega(\alpha), where \alpha{} is in A. Consider the subshift (X, T), where X is the shift orbit closure of f^\omega(\alpha) and ...
Cubefree words with many squares
(Discrete Mathematics and Theoretical Computer Science, 2014-05-13)
We construct infinite cubefree binary words containing exponentially many distinct squares of length n . We also show that for every positive integer n , there is a cubefree binary square of length 2n.
Avoiding three consecutive blocks of the same size and same sum
(Association of Computing Machinery, 2014-04)
We show that there exists an infinite word over the alphabet {0,1,3,4} containing no three consecutive blocks of the same size and the same sum. This answers an open problem of Pirillo and Varricchio from1994.