WikiDer > Повторяющееся слово

Recurrent word

В математике повторяющееся слово или же последовательность бесконечное слово над конечным алфавитом, в котором каждый фактор встречается бесконечно много раз.[1][2][3] Бесконечное слово повторяется тогда и только тогда, когда оно полуторка.[4][5]

А равномерно повторяющееся слово является повторяющимся словом, в котором для любого данного фактора Икс в последовательности есть некоторая длина пИкс (часто намного длиннее, чем длина Икс) такие, что Икс появляется в каждый блок длины пИкс.[1][6][7] Условия минимальная последовательность[8] и почти периодическая последовательность (Мучник, Семенов, Ушаков, 2003).

Примеры

  • Самый простой способ сделать повторяющуюся последовательность - сформировать периодическая последовательность, в котором последовательность полностью повторяется после заданного числа м шагов. Тогда такая последовательность будет равномерно рекуррентной и пИкс можно задать любое кратное м это больше, чем в два раза длиннее Икс. Рекуррентная последовательность, которая в конечном итоге является периодической, является чисто периодической.[2]
  • В Последовательность Туэ – Морса равномерно повторяющийся без быть периодическим или даже в конечном итоге периодическим (то есть периодическим после некоторого непериодического начального сегмента).[9]
  • Все Штурмские слова равномерно повторяющиеся.[10]

Рекомендации

  1. ^ а б Lothaire (2011) стр. 30
  2. ^ а б Аллуш и Шаллит (2003), стр.325
  3. ^ Пифей Фогг (2002) стр.2
  4. ^ Lothaire (2011) стр. 141
  5. ^ Berstel et al (2009) стр.133.
  6. ^ Берте и Риго (2010) стр.7
  7. ^ Аллуш и Шаллит (2003), стр.328.
  8. ^ Пифей Фогг (2002) стр.6
  9. ^ Lothaire (2011) стр.31
  10. ^ Берте и Риго (2010) с.177
  • Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения. Издательство Кембриджского университета. ISBN 978-0-521-82332-6. Zbl 1086.11015.
  • Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Кристоффель слова и повторы словами. Серия монографий CRM. 27. Провиденс, Род-Айленд: Американское математическое общество. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
  • Берте, Валери; Риго, Мишель, ред. (2010). Комбинаторика, автоматы и теория чисел. Энциклопедия математики и ее приложений. 135. Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-51597-9. Zbl 1197.68006.
  • Лотэр, М. (2011). Алгебраическая комбинаторика слов. Энциклопедия математики и ее приложений. 90. С предисловием Жана Берштеля и Доминика Перрена (Перепечатка изд. В твердом переплете 2002 г.). Издательство Кембриджского университета. ISBN 978-0-521-18071-9. Zbl 1221.68183.
  • Пифей Фогг, Н. (2002). Берте, Валери; Ференци, Себастьен; Mauduit, Christian; Сигель, Энн (ред.). Подстановки в динамике, арифметике и комбинаторике. Конспект лекций по математике. 1794. Берлин: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.
  • An. Мучник, А. Семенов, М. Ушаков, Почти периодические последовательности, ТМФ. Comput. Sci. том 304, номер 1-3 (2003), 1-33.