Displaying similar documents to “Corrigendum: On multiperiodic words”

Efficient validation and construction of border arrays and validation of string matching automata

Jean-Pierre Duval, Thierry Lecroq, Arnaud Lefebvre (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We present an on-line linear time and space algorithm to check if an integer array is the border array of at least one string built on a bounded or unbounded size alphabet . First of all, we show a bijection between the border array of a string and the skeleton of the DFA recognizing Σ*ω, called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array...

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

Return words in Sturmian and episturmian words

Jacques Justin, Laurent Vuillon (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Considering each occurrence of a word in a recurrent infinite word, we define the set of return words of to be the set of all distinct words beginning with an occurrence of and ending exactly just before the next occurrence of in the infinite word. We give a simpler proof of the recent result (of the second author) that an infinite word is Sturmian if and only if each of its factors has exactly two return words in it. Then, considering episturmian infinite words, which are a natural generalization...