## Search

Now showing items 1-10 of 25

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

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

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

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

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

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

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

#### Infinite words containing squares at every position

(EDP Sciences, 2010)

Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve ...