Sesquipower - Sesquipower

В математике полуторка или же Зимин слово это нить над алфавитом с одинаковыми префикс и суффикс. Sesquipowers неизбежные модели, в том смысле, что все достаточно длинные строки содержат одну.

Формальное определение

Формально пусть А быть алфавитом и А^∗ быть свободный моноид конечных строк надА. Каждое непустое слово ш в А⁺ является полуторной силой порядка 1. Если ты это сила порядка п тогда любое слово ш = уву это сила порядка п + 1.^[1] В степень непустого слова ш это наибольшее целое число d такой, что ш это сила порядка d.^[2]

Биидеальная последовательность

А биидеальная последовательность это последовательность слов ж_я куда ж₁ в А⁺ и

${\displaystyle f_{i+1}=f_{i}g_{i}f_{i}\ }$

для некоторых грамм_я в А^∗ и я ≥ 1. Степень слова ш таким образом, длина самой длинной биидеальной последовательности, оканчивающейся на ш.^[2]

Неизбежные закономерности

Для конечного алфавита А на k буквы, есть целое число M в зависимости от k и п, так что любое слово длины M имеет фактор, который является полуторной силой порядка по крайней мере п. Мы выражаем это, говоря, что полуторные неизбежные модели.^[3][4]

Полуторки в бесконечной последовательности

Для бесконечной бидидальной последовательности отметим, что каждая ж_я является префиксом ж_я+1 и так ж_я сходятся к бесконечной последовательности

${\displaystyle f=f_{1}g_{1}f_{1}g_{2}f_{1}g_{1}f_{1}g_{3}f_{1}\cdots \ }$

Мы определяем бесконечное слово как полуторную степень, если оно является пределом бесконечной биидеальной последовательности.^[5] Бесконечное слово является полуторной силой тогда и только тогда, когда оно повторяющееся слово,^[5][6] то есть каждый фактор встречается бесконечно часто.^[7]

Зафиксируем конечный алфавит А и предположим общий заказ по буквам. Для заданных целых чисел п и п, каждое достаточно длинное слово в А^∗ имеет либо фактор, который является п-мощность или фактор, который п-экипировка; в последнем случае фактор имеет п-факторизация в Слова Линдона.^[6]

Смотрите также

• Шаблон ABACABA

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

1. Lothaire (2011) стр. 135
2. Lothaire (2011) стр. 136
3. Lothaire (2011) стр. 137
4. Берстел и др. (2009) стр.132
5. Лотиара (2011) стр. 141
6. Berstel et al (2009) стр.133.
7. Lothaire (2011) стр. 30

• Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Кристоффель слова и повторы словами. Серия монографий CRM. 27. Провиденс, Род-Айленд: Американское математическое общество. ISBN  978-0-8218-4480-9. Zbl  1161.68043.
• Лотэр, М. (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.