Повторяющееся слово
В математике повторяющееся слово или последовательность — это бесконечное слово в конечном алфавите, в котором каждый фактор встречается бесконечно много раз. [ 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 ]
Примечания
[ редактировать ]- ^ Jump up to: а б Лотарь (2011), с. 30
- ^ Jump up to: а б Аллуш и Шалит (2003) стр.325
- ^ Пифей Фогг (2002) стр.2
- ^ Лотарь (2011) с. 141
- ^ Берстель и др. (2009) стр.133
- ^ Берте и Риго (2010) стр.7
- ^ Аллуш и Шалит (2003) стр.328
- ^ Пифей Фогг (2002) стр.6
- ^ Лотарь (2011) стр.31
- ^ Берте и Риго (2010) стр.177
Ссылки
[ редактировать ]- Аллуш, Жан-Поль; Шалит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN 978-0-521-82332-6 . Збл 1086.11015 .
- Берстель, Жан ; Лауве, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Слова Кристоффеля и повторы в словах . Серия монографий по CRM. Том. 27. Провиденс, Род-Айленд: Американское математическое общество . ISBN 978-0-8218-4480-9 . Коллекция 1161.68043 .
- Берта, Валери ; Риго, Мишель, ред. (2010). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том. 135. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-51597-9 . Збл 1197.68006 .
- Лотер, М. (2011). Алгебраическая комбинаторика на словах . Энциклопедия математики и ее приложений. Том. 90. С предисловием Жана Берстеля и Доминика Перрена (перепечатка издания 2002 г. в твердом переплете). Издательство Кембриджского университета. 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.
 | Эта алгеброй статья, связанная с , незавершена . Вы можете помочь Википедии, расширив ее . |