## Search

Now showing items 1-10 of 25

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

#### Words with many palindrome pair factors

(The Electronic Journal of Combinatorics, 2015-10-30)

Motivated by a conjecture of Frid, Puzynina, and Zamboni, we investigate infinite words with the property that for infinitely many n, every length-n factor is a product of two palindromes. We show that every Sturmian word ...

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

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

#### Abelian complexity of fixed point of morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1

(Integers, 2014-02-20)

We study the combinatorics of vtm, a variant of the Thue-Morse word generated by the non-uniform morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1 starting with 0. This infinite ternary sequence appears a lot in the literature and finds ...

#### Avoiding approximate repetitions with respect to the longest common subsequence distance

(Mathematical Sciences Publishers, 2015-09-17)

Ochem, Rampersad, and Shallit gave various examples of infinite words avoiding what they called approximate repetitions. An approximate repetition is a factor of the form x x', where x and x' are close to being identical. ...

#### Multi-dimensional sets recognizable in all abstract numeration systems

(EDP Sciences, 2011)

We prove that the subsets of Nd that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.

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

#### Dejean's conjecture holds for n ≥ 27

(EDP Sciences, 2009)

We show that Dejean’s conjecture holds for n ≥ 27. This brings the final resolution of the conjecture by the approach of Moulin Ollagnier within range of the computationally feasible.

#### Growth rate of binary words avoiding xxxR

(Elsevier, 2016-01)

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