## Search

Now showing items 11-20 of 25

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

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

#### The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially

(2004-06-19)

We show that the number of ternary words of length n avoiding abelian cubes grows
faster than r^n, where r = 2^{1/24}

#### Binary Words Containing Infinitely Many Overlaps

(The Electronic Journal of Combinatorics, 2006-09-22)

We characterize the squares occurring in infinite overlap-free binary words and construct various α power-free binary words containing infinitely many overlaps.

#### Cyclic Complexity of Some Infinite Words and Generalizations

(Integers, 2018-03)

Cassaigne et al. introduced the cyclic complexity function c_x(n), which gives the number of cyclic conjugacy classes of length-n factors of a word x. We study the behavior of this function for the Fibonacci word f and the ...

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