Сесквипауэр
В математике полуторная степень или слово Зимина представляет собой строку над алфавитом с идентичным префиксом и суффиксом . Полуторные степени являются неизбежными шаблонами в том смысле, что все достаточно длинные строки содержат их.
Формальное определение
[ редактировать ]Формально, пусть A — алфавит и A ∗ — свободный моноид конечных струн над A . Каждое непустое слово w в A + — полуторная степень порядка 1. Если u — полуторная степень порядка n, то любое слово w = uvu является полуторной степенью порядка n + 1. [1] Степень — это непустого слова w наибольшее целое число d такое, что w — полуторная степень порядка d . [2]
Биидеальная последовательность
[ редактировать ]Биидеальная последовательность — это последовательность слов fi , где f 1 находится в A + и
для числа некоторого в A ∗ и i ≥ 1. Таким образом, степень слова w равна длине самой длинной биидеальной последовательности, оканчивающейся на w . [2]
Неизбежные закономерности
[ редактировать ]Для конечного алфавита A на k буквах существует целое число M, зависящее от k и n , такое, что любое слово длины M имеет множитель, который является полуторной степенью порядка не ниже n . Мы выражаем это, говоря, что полуторные степени являются неизбежными закономерностями . [3] [4]
Полуторные степени в бесконечных последовательностях
[ редактировать ]бесконечную биидеальную последовательность, отметим, что каждый f i является префиксом fi Учитывая +1 и поэтому f i сходится к бесконечной последовательности
Мы определяем бесконечное слово как полуторную степень, если оно является пределом бесконечной биидеальной последовательности. [5] Бесконечное слово является полуторной степенью тогда и только тогда, когда оно является повторяющимся словом . [5] [6] то есть каждый фактор встречается бесконечно часто. [7]
Зафиксируйте конечный алфавит A и предположите полный порядок букв. Для заданных целых чисел p и n каждое достаточно длинное слово в A ∗ имеет либо множитель, который представляет собой p -степень, либо множитель, который представляет собой n -полуторную степень; в последнем случае фактор имеет n - факторизацию в слова Линдона . [6]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Лотарь (2011) с. 135
- ^ Jump up to: а б Лотарь (2011), с. 136
- ^ Лотарь (2011) с. 137
- ^ Берстель и др. (2009) стр.132
- ^ Jump up to: а б Лотиаре (2011), с. 141
- ^ Jump up to: а б Берстель и др. (2009), стр. 133.
- ^ Лотарь (2011) с. 30
- Берстель, Жан ; Лауве, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Слова Кристоффеля и повторы в словах . Серия монографий по CRM. Том. 27. Провиденс, Род-Айленд: Американское математическое общество . ISBN 978-0-8218-4480-9 . Артикул 1161.68043 .
- Лотер, М. (2011). Алгебраическая комбинаторика на словах . Энциклопедия математики и ее приложений. Том. 90. С предисловием Жана Берстеля и Доминика Перрена (перепечатка издания 2002 г. в твердом переплете). Издательство Кембриджского университета. ISBN 978-0-521-18071-9 . Артикул 1221.68183 .
- Пифей Фогг, Н. (2002). Берте, Валери ; Ференци, Себастьен; Модуит, Кристиан; Сигел, Энн (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN 3-540-44141-7 . Збл 1014.11015 .