On Two Stronger Versions of Dejean's Conjecture / Tunev Igor N.,Shur Arseny M. // . - 2012. - V. 7464, l. . - P. 800-812.

ISSN/EISSN:

0302-9743 / нет данных

Type:

Proceedings Paper

Abstract:

Repetition threshold is the smallest number RT(n) such that infinitely many n-ary words contain no repetition of order greater than RT(n). These ``extremal{''} repetition-free words are called threshold words. All values of RT(n) are now known, since the celebrated Dejean's conjecture (1972) was finally settled in 2009. We study two questions about threshold words. First, does the number of n-ary threshold words grow exponentially with length? This is the case for 3 <= n <= 10, and a folklore conjecture suggests an affirmative answer for all n >= 3. Second, are there infinitely many n-ary threshold words containing only finitely many different repetitions of order RT(n)? The answer is ``yes{''} for n = 3, but nothing was previously known about bigger alphabets. For odd n = 7, 9, ... , 101, we prove the strongest possible result in this direction. Namely, there are exponentially many n-ary threshold words containing no repetitions of order RT(n) except for the repeats of just one letter.

Author keywords:

FREE WORDS; ALPHABETS; SYMBOLS

DOI:

нет данных

Web of Science ID:

ISI:000371253900069

Соавторы в МНС:

—

Другие поля

Поле	Значение
Editor	Rovan, B and Sassone, V and Widmayer, P
Booktitle	MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2012
Series	Lecture Notes in Computer Science
Note	37th International Symposium on Mathematical Foundations of Computer Science, (MFCS), Bratislava, SLOVAKIA, AUG 27-31, 2012
Organization	Slovak Soc Comp Sci; Comenius Univ, Fac Math Phys \& Informat
Publisher	SPRINGER-VERLAG BERLIN
Address	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
Language	English
ISBN	978-3-642-32589-2; 978-3-642-32588-5
Keywords-Plus	FREE WORDS; ALPHABETS; SYMBOLS
Research-Areas	Computer Science; Mathematics; Science \& Technology - Other Topics
Web-of-Science-Categories	Computer Science, Theory \& Methods; Mathematics; Logic
Author-Email	itnvi@mail.ru arseny.shur@usu.ru
Number-of-Cited-References	15
Doc-Delivery-Number	BE3TA