Критический показатель слова

В математике и информатике критический показатель конечной или бесконечной последовательности символов в конечном алфавите описывает наибольшее количество раз, которое может повториться непрерывная подпоследовательность. Например, критический показатель «Миссисипи» равен 7/3, поскольку он содержит строку «иссисси» длиной 7 и периодом 3.

Если w — бесконечное слово в алфавите A, а x — конечное слово в A , то x говорят, что встречается в w с показателем α для положительного действительного α, если существует фактор y слова w с y = x ^а x ₀ , где x ₀ — префикс x , a — целая часть α, а длина | й | = α | x |: мы говорим, что y является α-степенью . Слово w является альфа-бесстепенным , если оно не содержит множителей, которые являются β-степенями для любого β ≥ α.

Критический показатель для w - это верхняя грань α, для которой w имеет α-степени, или, что то же самое, нижняя грань α, для которой w не имеет α-степени.

Определение

Если $\mathbf {w}$ — слово (возможно, бесконечное), то критический показатель степени $\mathbf {w}$ определяется как

$E(\mathbf {w} )=\sup\{r\in \mathbb {Q} ^{\geq 1}:\mathbf {w} \,{\text{ contains an }}\,r{\text{-power}}\}$

где $\mathbb {Q} ^{\geq 1}=\{q\in \mathbb {Q} :q\geq 1\}$.

Примеры

• Критический показатель слова Фибоначчи равен (5 + √ 5 )/2 ≈ 3,618.
• Критический показатель последовательности Туэ – Морса равен 2. Слово содержит квадраты произвольной длины, но в любом множителе xxb буква b не является префиксом x .

Характеристики

• Критический показатель степени может принимать любое действительное значение больше 1.
• Критический показатель морфного слова в конечном алфавите либо бесконечен, либо представляет собой алгебраическое число степени, не превышающей размер алфавита.

Порог повторения

Порог повторения алфавита A из n букв — это минимальный критический показатель бесконечных слов над A : очевидно, что это значение RT( n ) зависит только от n . При n = 2 любое двоичное слово длины четыре имеет показатель степени 2, а поскольку критический показатель последовательности Туэ–Морса равен 2, порог повторения для двоичных алфавитов равен RT(2) = 2. Известно, что RT(3) = 7/4, RT(4) = 7/5 и что для n ≥5 имеем RT( n ) ≥ n /( n -1). Предполагается, что последнее значение является истинным, и это установлено для 5 ≤ n ≤ 14 и для n ≥ 33.

См. также

• Критический показатель физической системы

Ссылки

• Аллуш, Жан-Поль; Шалит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN  978-0-521-82332-6 . Збл   1086.11015 .
• Берстель, Жан; Лауве, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Слова Кристоффеля и повторы в словах . Серия монографий по CRM. Том. 27. Провиденс, Род-Айленд: Американское математическое общество . ISBN  978-0-8218-4480-9 . Артикул   1161.68043 .
• Кригер, Далия (2006). «О критических показателях в неподвижных точках нестирающихся морфизмов». В Ибарре, Оскар Х.; Данг, Чжэ (ред.). Развитие теории языка: материалы 10-й международной конференции, DLT 2006, Санта-Барбара, Калифорния, США, 26–29 июня 2006 г. Конспекты лекций по информатике. Том. 4036. Шпрингер-Верлаг . стр. 280–291. ISBN  3-540-35428-Х . Збл   1227.68074 .
• Кригер, Д.; Шалит, Дж. (2007). «Каждое действительное число больше единицы является критическим показателем» . Теор. Вычислить. Наука . 381 (1–3): 177–182. дои : 10.1016/j.tcs.2007.04.037 .
• Лотер, М. (2011). Алгебраическая комбинаторика на словах . Энциклопедия математики и ее приложений. Том. 90. С предисловием Жана Берстеля и Доминика Перрена (перепечатка издания 2002 г. в твердом переплете). Издательство Кембриджского университета. ISBN  978-0-521-18071-9 . Артикул   1221.68183 .
• Пифей Фогг, Н. (2002). Берта, Валери ; Ференци, Себастьян; Модуит, Кристиан; Сигел, А. (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN  3-540-44141-7 . Збл   1014.11015 .