Функция сложности

В информатике функция сложности слова ) — это функция , или строки (конечная или бесконечная последовательность символов из некоторого алфавита которая подсчитывает количество различных факторов (подстрок последовательных символов) этой строки. В более общем смысле, функция сложности формального языка (набора конечных строк) подсчитывает количество различных слов заданной длины.

Функция сложности слова

Пусть u — (возможно, бесконечная) последовательность символов алфавита. Определите функцию p _u ( n ) натурального числа n — это количество различных факторов (последовательных подстрок) длины n из строки u .

Для строки u длины не менее n в алфавите размера k мы, очевидно, имеем

$1\leq p_{u}(n)\leq k^{n}\ ,$

границы, достигаемые постоянным словом и разделительным словом , например, слово Champernowne соответственно. Для бесконечных слов u мы имеем p _u ( n ) ограниченным, если u в конечном итоге периодично (конечная, возможно, пустая последовательность, за которой следует конечный цикл). И наоборот, если p _u ( n ) ≤ n для некоторого n , то u в конечном итоге периодично.

Апериодическая последовательность — это последовательность, которая не является в конечном итоге периодической. Апериодическая последовательность имеет строго возрастающую функцию сложности (это теорема Морса–Хедлунда ), поэтому p ( n ) равно как минимум n +1.

Множество S конечных двоичных слов сбалансировано , если для каждого n подмножество Sn _слов длины n обладает тем свойством, что вес Хэмминга слов из принимает _Sn не более двух различных значений. – Сбалансированная последовательность это последовательность, для которой набор факторов сбалансирован. Сбалансированная последовательность имеет функцию сложности не более n +1.

Слово Штурма в двоичном алфавите — это слово с функцией сложности n + 1. Последовательность является штурмовой тогда и только тогда, когда она сбалансирована и апериодична. Примером может служить слово Фибоначчи . В более общем смысле, слово Штурма в алфавите размера k — это слово со сложностью n + k −1. Слово Арну-Рози в троичном алфавите имеет сложность 2 n + 1: примером является слово Трибоначчи .

Для повторяющихся слов , в которых каждый фактор появляется бесконечно часто, функция сложности почти характеризует набор факторов: если s — повторяющееся слово с той же функцией сложности, что и t , то s имеет тот же набор факторов, что и t или δ t. где δ обозначает морфизм удвоения букв a → aa .

Функция сложности языка

Пусть L — язык над алфавитом и определим функцию p _L ( n ) натурального числа n как количество различных слов длины n в L. Таким образом, функция сложности слова — это функция сложности языка, состоящего из факторов этого слова.

Функция сложности языка менее ограничена, чем функция сложности слова. Например, она может быть ограниченной, но не постоянной: функция сложности регулярного языка $a(bb)^{*}a$ принимает значения 3 и 4 при нечетном и четном n ≥2 соответственно. Существует аналог теоремы Морса–Хедлунда: если сложность L удовлетворяет условию p _L ( n ) ⩽ n для некоторого n , то p _L ограничен и существует конечный язык F такой, что

$L\subseteq \{xy^{k}z:x,y,z\in F,\ k\in \mathbb {N} \}\ .$

Полиномиальный — это язык , или разреженный язык для которого функция сложности p ( n ) ограничена фиксированной степенью n . Регулярный язык , который не является полиномиальным, является экспоненциальным : существует бесконечно много n, для которых p ( n ) больше k. ^н для некоторого фиксированного k > 1.

Связанные понятия

Топологическая энтропия бесконечной последовательности u определяется формулой

$H_{\mathrm {top} }(u)=\lim _{n\rightarrow \infty }{\frac {\log p_{u}(n)}{n\log k}}\ .$

Предел существует, поскольку логарифм функции сложности субаддитивен . Каждое действительное число от 0 до 1 встречается, когда применима топологическая энтропия некоторой последовательности: которые можно считать равномерно повторяющимися или даже однозначно эргодично.

Если x — действительное число и b — целое число ≥ 2, то функция сложности x в базе b — это функция сложности p ( x , b , n ) последовательности цифр x, записанной в базе b .Если x — иррациональное число , то p ( x , b , n ) ≥ n +1; если x рационально , то p ( x , b , n ) ≤ C для некоторой константы C, зависящей от x и b . Предполагается, что для алгебраически иррационального x сложность равна b ^н (что последовало бы, если бы все такие числа были нормальными ), но все, что известно в этом случае, это то, что p растет быстрее, чем любая линейная функция от n .

Абелева функция сложности p ^аб ( n ) аналогичным образом подсчитывает количество вхождений различных факторов заданной длины n , где теперь мы идентифицируем факторы, которые отличаются только перестановкой позиций. Очевидно, р ^аб ( п ) ≤ п ( п ). Абелева сложность последовательности Штурма удовлетворяет условию p ^аб ( п ) = 2.

Ссылки

• Аллуш, Жан-Поль; Шалит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN  978-0-521-82332-6 . Збл   1086.11015 .
• Берстель, Жан; Лауве, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Слова Кристоффеля и повторы в словах . Серия монографий по CRM. Том. 27. Провиденс, Род-Айленд: Американское математическое общество . ISBN  978-0-8218-4480-9 . Артикул   1161.68043 .
• Берта, Валери ; Риго, Мишель, ред. (2010). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том. 135. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-51597-9 . Збл   1197.68006 .
• Бюжо, Янн (2012). Распределение по модулю единицы и диофантово приближение . Кембриджские трактаты по математике. Том. 193. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-11169-0 . Збл   1260.11001 .
• Кассень, Жюльен; Николя, Франсуа (2010). «Фактор сложности». В Берте, Валери ; Риго, Мишель (ред.). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том. 135. Кембридж: Издательство Кембриджского университета . стр. 163–247. ISBN  978-0-521-51597-9 . Збл   1216.68204 .
• Лотер, М. (2011). Алгебраическая комбинаторика на словах . Энциклопедия математики и ее приложений. Том. 90. С предисловием Жана Берстеля и Доминика Перрена (перепечатка издания 2002 г. в твердом переплете). Издательство Кембриджского университета. ISBN  978-0-521-18071-9 . Артикул   1221.68183 .
• Пифей Фогг, Н. (2002). Берта, Валери ; Ференци, Себастьен; Модуит, Кристиан; Сигел, А. (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN  3-540-44141-7 . Збл   1014.11015 .