Displaying similar documents to “Morphisms preserving the set of words coding three interval exchange”

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

The number of binary rotation words

A. Frid, D. Jamet (2014)

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

Similarity:

We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length . We also give the precise asymptotics for it, which happens to be ( ). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov [39 (1982) 67–84], then independently by Mignosi [82 (1991) 71–84], and others.

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

On the distribution of characteristic parameters of words

Arturo Carpi, Aldo de Luca (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

For any finite word on a finite alphabet, we consider the basic parameters and of defined as follows: is the minimal natural number for which has no right special factor of length and is the minimal natural number for which has no repeated suffix of length . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words ...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine...

Universality in the bulk of the spectrum for complex sample covariance matrices

Sandrine Péché (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider complex sample covariance matrices = (1/)* where is a × random matrix with i.i.d. entries , 1 ≤ ≤ , 1 ≤ ≤ , with distribution . Under some regularity and decay assumptions on , we prove universality of some local eigenvalue statistics in the bulk of the spectrum in the limit where → ∞ and lim→∞ / = for any real number ∈ (0, ∞).

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