## Search

Now showing items 1-10 of 26

#### 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 ...

#### 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 ...

#### A Note on Antichains of Words

(The Electronic Journal of Combinatorics, 1995-10-14)

We can compress the word 'banana' as xyyz, where x= 'b', y= 'an',z= 'a'. We say that 'banana' encounters yy. Thus a 'coded' version of yy shows up in 'banana'. The relation 'u encounters w' is transitive, and thus generates ...

#### 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, ...

#### 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.

#### 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 ...

#### 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 ...

#### 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 ...

#### 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.

#### Avoidability index for binary patterns with reversal

(2017)

For every pattern p over the alphabet {x,x^R,y,y^R}, we specify the least k such that p is k-avoidable.