Повторяющееся слово
В математике рекуррентное слово или последовательность — это бесконечное слово в конечном алфавите, в котором каждый фактор встречается бесконечно много раз. [1] [2] [3] Бесконечное слово является рекуррентным тогда и только тогда, когда оно является полуторастепенью . [4] [5]
Равномерно рекуррентное слово — это рекуррентное слово, в котором для любого заданного фактора X в последовательности существует некоторая длина n X (часто намного больше длины X ), такая, что X появляется в каждом блоке длины n X . [1] [6] [7] Также используются термины минимальная последовательность [8] и почти периодическая последовательность (Мучник, Семенов, Ушаков 2003).
Примеры
- Самый простой способ сделать рекуррентную последовательность — сформировать периодическую последовательность , где последовательность полностью повторяется после заданного числа m шагов. Такая последовательность затем равномерно рекуррентна и n X может быть установлена в любое кратное m , которое больше, чем удвоенная длина X. Рекуррентная последовательность, которая в конечном счете периодична, является чисто периодической. [2]
- Последовательность Туэ-Морса является равномерно рекуррентной, не будучи ни периодической, ни даже периодической в конечном итоге (то есть периодической после некоторого непериодического начального сегмента). [9]
- Все слова Штурма являются одинаково повторяющимися. [10]
Примечания
- ^ ab Lothaire (2011) стр. 30
- ^ ab Allouche & Shallit (2003) стр.325
- ^ Пифей Фогг (2002) стр.2
- ^ Лотер (2011) стр. 141
- ^ Берстель и др. (2009) стр.133
- ^ Берте и Риго (2010) стр.7
- ^ Аллуш и Шалит (2003) стр.328
- ^ Пифей Фогг (2002) стр.6
- ^ Лотер (2011) стр.31
- ^ Берте и Риго (2010) стр.177
Ссылки
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Автоматические последовательности: теория, приложения, обобщения . Cambridge University Press . ISBN 978-0-521-82332-6. Збл 1086.11015.
- Berstel, Jean ; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Комбинаторика слов. Слова Кристоффеля и повторения в словах. Серия монографий CRM. Том 27. Providence, RI: Американское математическое общество . ISBN 978-0-8218-4480-9. Збл 1161.68043.
- Берте, Валери ; Риго, Мишель, ред. (2010). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том 135. Кембридж: Cambridge University Press . ISBN 978-0-521-51597-9. Збл 1197.68006.
- Лотер, М. (2011). Алгебраическая комбинаторика слов . Энциклопедия математики и ее приложений. Т. 90. С предисловием Жана Берстеля и Доминика Перрена (Переиздание издания 2002 года в твердом переплете). Cambridge University Press. ISBN 978-0-521-18071-9. Збл 1221.68183.
- Пифей Фогг, Н. (2002). Берта, Валери ; Ференци, Себастьян; Модуит, Кристиан; Сигел, Энн (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN 3-540-44141-7. Збл 1014.11015.
- Ан. Мучник, А. Семенов, М. Ушаков, Почти периодические последовательности, Теор. вычисл. наук. т.304, №1-3 (2003), 1-33.
