Displaying similar documents to “Episturmian morphisms and a Galois theorem on continued fractions”

Finite repetition threshold for large alphabets

Golnaz Badkobeh, Maxime Crochemore, Michaël Rao (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We investigate the finite repetition threshold for -letter alphabets, ≥ 4, that is the smallest number for which there exists an infinite -free word containing a finite number of -powers. We show that there exists an infinite Dejean word on a 4-letter alphabet (a word without factors of exponent more than 7/5 ) containing only two 7/5 -powers. For a 5-letter alphabet, we show that there exists an infinite Dejean word containing only 60 5/4 -powers, and we conjecture...

Look and Say Fibonacci

Patrice Séébold (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The () derivative of a word is obtained by writing the number of consecutive equal letters when the word is spelled from left to right. For example, 1 1 2 3 3) = 2 1 1 2 2 3 (two , one , two ). We start the study of the behaviour of binary words generated by morphisms under the operator, focusing in particular on the Fibonacci word.

Some algorithms to compute the conjugates of Episturmian morphisms

Gwenael Richomme (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Episturmian morphisms generalize Sturmian morphisms. They are defined as compositions of exchange morphisms and two particular morphisms , and . Epistandard morphisms are the morphisms obtained without considering . In [14], a general study of these morphims and of conjugacy of morphisms is given. Here, given a decomposition of an Episturmian morphism over exchange morphisms and , we consider two problems: how to compute a decomposition of one conjugate of ; how to compute...

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...