WikiDer > Sesquipower

Sesquipower

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

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

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

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

А биидеальная последовательность это последовательность слов жя куда ж1 в А+ и

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

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

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

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

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

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

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

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

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

  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.