Search
Now showing items 1-10 of 26
Extremal words in morphic subshifts
(Elsevier, 2014-01-22)
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
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 ...
Combinatorics and Algorithmics of Strings
(Dagstuhl Publishing, 2014-03-09)
Strings (aka sequences or words) form the most basic and natural data structure. They occur whenever information is electronically transmitted (as bit streams), when natural language text is spoken or written down (as words ...
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, ...
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.
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 ...