Displaying similar documents to “A test-set for k -power-free binary morphisms”

A generator of morphisms for infinite words

Pascal Ochem (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

We present an algorithm which produces, in some cases, infinite words avoiding both large fractional repetitions and a given set of finite words. We use this method to show that all the ternary patterns whose avoidability index was left open in Cassaigne's thesis are 2-avoidable. We also prove that there exist exponentially many 7 4 + -free ternary words and 7 5 + -free 4-ary words. Finally we give small morphisms for binary words containing only the squares , 1 and (01)² and for binary words...

On the distribution of characteristic parameters of words

Arturo Carpi, Aldo de Luca (2002)

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

Similarity:

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

Equations on partial words

Francine Blanchet-Sadri, D. Dakota Blair, Rebeca V. Lewis (2009)

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

Similarity:

It is well-known that some of the most basic properties of words, like the commutativity ( x y = y x ) and the conjugacy ( x z = z y ), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation x m y n = z p has only periodic solutions in a free monoid, that is, if x m y n = z p holds with integers m , n , p ≥ 2 , then there exists a word w such that x , y , z are powers of w . This result, which received a lot of attention, was first proved...