Currently displaying 1 – 4 of 4

Showing per page

Order by Relevance | Title | Year of publication

Fewest repetitions in infinite binary words

Golnaz BadkobehMaxime Crochemore — 2012

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

A square is the concatenation of a nonempty word with itself. A word has period if its letters at distance match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property, and...

Fewest repetitions in infinite binary words

Golnaz BadkobehMaxime Crochemore — 2012

RAIRO - Theoretical Informatics and Applications

A square is the concatenation of a nonempty word with itself. A word has period if its letters at distance match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property, and...

Fewest repetitions in infinite binary words

Golnaz BadkobehMaxime Crochemore — 2012

RAIRO - Theoretical Informatics and Applications

A square is the concatenation of a nonempty word with itself. A word has period if its letters at distance match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property, and...

Finite repetition threshold for large alphabets

Golnaz BadkobehMaxime CrochemoreMichaël Rao — 2014

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

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 that this number...

Page 1

Download Results (CSV)