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