## Search

Now showing items 1-10 of 25

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

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

#### Shuffling and unshuffling

(Bulletin of the European Association for Theoretical Computer Science, 2012)

We consider various shuffling and unshuffling operations on languages and words, and examine their closure properties. Although the main goal is to provide some good and novel exercises and examples for undergraduate formal ...

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

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

#### The minimal automaton recognizing mN in a linear numeration system

(Integers, 2011-12-02)

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component ...

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

(2016-02-14)

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 inﬁnite ternary sequence appears a lot in the literature and ﬁnds ...

#### Automaticity of Primitive Words and Irreducible Polynomials

(Discrete Mathematics and Theoretical Computer Science, 2013)

If L is a language, the automaticity function AL(n) (resp. NL(n)) of L counts the number of states of a smallest deterministic (resp. non-deterministic) finite automaton that accepts a language that agrees with L on all ...

#### Overlap-Free Words and Generalizations

(University of Winnipeg, 2007)

The study of combinatorics on words dates back at least to the beginning of the
20th century and the work of Axel Thue. Thue was the first to give an example of an infinite word over a three letter alphabet that contains ...