Функция сложности
В информатике функция сложности слова ) — это функция , или строки (конечная или бесконечная последовательность символов из некоторого алфавита которая подсчитывает количество различных факторов (подстрок последовательных символов) этой строки. В более общем смысле, функция сложности формального языка (набора конечных строк) подсчитывает количество различных слов заданной длины.
Функция сложности слова
[ редактировать ]Пусть u — (возможно, бесконечная) последовательность символов алфавита. Определите функцию p u ( n ) положительного целого числа n — это количество различных факторов (последовательных подстрок) длины n из строки u . [1] [2] [3] [4] [5]
Для строки u длины не менее n в алфавите размера k мы, очевидно, имеем
границы, достигаемые постоянным словом и разделительным словом , [6] например, слово Champernowne соответственно. [7] Для бесконечных слов u мы имеем p u ( n ) ограниченным, если u в конечном итоге периодично (конечная, возможно, пустая последовательность, за которой следует конечный цикл). И наоборот, если p u ( n ) ≤ n для некоторого n , то u в конечном итоге периодично. [3] [8]
Апериодическая последовательность — это последовательность, которая не является в конечном итоге периодической. Апериодическая последовательность имеет строго возрастающую функцию сложности (это теорема Морса–Хедлунда ), [9] [10] поэтому p ( n ) равно как минимум n +1. [11]
Множество S конечных двоичных слов сбалансировано , если для каждого n подмножество Sn слов длины n обладает тем свойством, что вес Хэмминга слов из принимает Sn не более двух различных значений. – Сбалансированная последовательность это последовательность, для которой набор факторов сбалансирован. [12] Сбалансированная последовательность имеет функцию сложности не более n +1. [13]
Слово Штурма в двоичном алфавите — это слово с функцией сложности n + 1. [14] Последовательность является штурмовой тогда и только тогда, когда она сбалансирована и апериодична. [2] [15] Примером может служить слово Фибоначчи . [14] [16] В более общем смысле, слово Штурма в алфавите размера k — это слово со сложностью n + k −1. Слово Арну-Рози в троичном алфавите имеет сложность 2 n + 1: [14] примером является слово Трибоначчи . [17]
Для повторяющихся слов , в которых каждый фактор появляется бесконечно часто, функция сложности почти характеризует набор факторов: если s — повторяющееся слово с той же функцией сложности, что и t , то s имеет тот же набор факторов, что и t или δ t. где δ обозначает морфизм удвоения букв a → aa . [18]
Функция сложности языка
[ редактировать ]Пусть L — язык над алфавитом и определим функцию p L ( n ) натурального числа n как количество различных слов длины n в L. [9] Таким образом, функция сложности слова — это функция сложности языка, состоящего из факторов этого слова.
Функция сложности языка менее ограничена, чем функция сложности слова. Например, она может быть ограниченной, но не постоянной: функция сложности регулярного языка принимает значения 3 и 4 при нечетном и четном n ≥2 соответственно. Существует аналог теоремы Морса–Хедлунда: если сложность L удовлетворяет условию p L ( n ) ⩽ n для некоторого n , то p L ограничен и существует конечный язык F такой, что [9]
Полиномиальный — это язык , или разреженный язык для которого функция сложности p ( n ) ограничена фиксированной степенью n . Регулярный язык , который не является полиномиальным, является экспоненциальным : существует бесконечно много n, для которых p ( n ) больше k. н для некоторого фиксированного k > 1. [19]
Связанные понятия
[ редактировать ]Топологическая энтропия бесконечной последовательности u определяется выражением
Предел существует, поскольку логарифм функции сложности субаддитивен . [20] [21] Каждое действительное число от 0 до 1 встречается, когда применима топологическая энтропия некоторой последовательности: [22] которые можно считать равномерно повторяющимися [23] или даже однозначно эргодично. [24]
Если 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 . [6] Предполагается, что для алгебраически иррационального x сложность равна b н (что последовало бы, если бы все такие числа были нормальными ), но все, что известно в этом случае, это то, что p растет быстрее, чем любая линейная функция от n . [25]
Абелева функция сложности p аб ( n ) аналогичным образом подсчитывает количество вхождений различных факторов заданной длины n , где теперь мы идентифицируем факторы, которые отличаются только перестановкой позиций. Очевидно, р аб ( п ) ≤ п ( п ). Абелева сложность последовательности Штурма удовлетворяет условию p аб ( п ) = 2. [26]
Ссылки
[ редактировать ]- ^ Лотарь (2011) стр.7
- ^ Jump up to: а б Лотарь (2011) стр.46
- ^ Jump up to: а б Пифей Фогг (2002) стр.3
- ^ Берстель и др. (2009) стр.82
- ^ Аллуш и Шалит (2003) стр.298
- ^ Jump up to: а б Бюжо (2012) стр.91
- ^ Кассень и Николя (2010) стр.165
- ^ Аллуш и Шалит (2003) стр.302
- ^ Jump up to: а б с Берте и Риго (2010) стр.166
- ^ Кассень и Николя (2010) стр.166
- ^ Лотарь (2011) стр.22
- ^ Аллуш и Шалит (2003) стр.313
- ^ Лотарь (2011) стр.48
- ^ Jump up to: а б с Пифей Фогг (2002) стр.6
- ^ Аллуш и Шалит (2003) стр.318
- ^ де Лука, Альдо (1995). «Свойство деления слова Фибоначчи». Письма об обработке информации . 54 (6): 307–312. дои : 10.1016/0020-0190(95)00067-М .
- ^ Пифей Фогг (2002) стр.368
- ^ Берстель и др. (2009) стр.84
- ^ Берте и Риго (2010) стр.136
- ^ Пифей Фогг (2002) стр.4
- ^ Аллуш и Шалит (2003) стр.303
- ^ Кассень и Николя (2010) стр.169
- ^ Берте и Риго (2010) стр.391
- ^ Берте и Риго (2010) стр.169
- ^ Берте и Риго (2010) стр.414
- ^ Бланше-Садри, Франсин; Фокс, Натан (2013). «Об асимптотической абелевой сложности морфических слов». В Беале, Мари-Пьер; Картон, Оливье (ред.). Развитие теории языка. Материалы 17-й Международной конференции DLT 2013, Марн-ла-Валле, Франция, 18-21 июня 2013 г. Конспекты лекций по информатике. Том. 7907. Берлин, Гейдельберг: Springer-Verlag . стр. 94–105. дои : 10.1007/978-3-642-38771-5_10 . ISBN 978-3-642-38770-8 . ISSN 0302-9743 .
- Аллуш, Жан-Поль; Шалит, Джеффри (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 .