Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Если ш бесконечное слово в алфавите А и х представляет собой конечное слово над А , то х называется происходить в ш с показателем а, для положительного вещественного а, если существует фактор у из ш с у = х х 0, где x 0 - это префикс x , a - целая часть α, а длина | y | ≥ α | x |: мы говорим, что y является α-степенью . Слово ш IS без α-степени, если он не содержит множителей, являющихся α-степенями. [1]

Критический показатель для ш является супремумом из а , для которых ш имеет a-силы, [2] или , что эквивалентно инфимуму из а , для которых ш является α-мощности , свободной. [3]

Примеры [ править ]

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

Свойства [ править ]

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

Порог повторения [ править ]

Порог повторения в алфавите А из п букв минимальный критический показатель бесконечных слов над A : очевидно , это значение RT ( п ) зависит только от п . При 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. [2] [4] Недавно М. Рао завершил доказательство для всех значений n .

См. Также [ править ]

Заметки [ править ]

  1. ^ Krieger (2006) p.281
  2. ^ a b Berstel et al (2009) стр.126
  3. ^ a b c d e Krieger (2006) с.280
  4. ^ a b Allouche & Shallit (2003) стр. 37
  5. ^ Krieger & Shallit (2007) .

Ссылки [ править ]

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