Steklov Institute of Mathematics at St.Petersburg

PREPRINT 22/2006


Юхани Карьюмяки, Юрий Лифшиц

РАЗРЕЖЕННАЯ ПЕРИОДИЧНОСТЬ

This preprint was accepted December 16, 2006

ABSTRACT:
В этой работе мы обобщаем классическое понятие периодичности. Слово называется
разреженно периодичным, если оно может быть разделено на несколько копий
частично определенного слова. Например слово XXYY является разреженно
периодическим, так как оно состоит из двух копий частично определенного слова X_Y.

Мы изучим это понятие, обсудим его свойства и представим алгоритм поиска
разреженных периодов минимального размера.  В процессе исследований нам
удалось ответить на два открытых вопроса, поставленных соответственно
Теро Харью и Нейлом Слоаном.
[Full text:
(.ps.gz)]


Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg