Функция сложности
Функция, которая подсчитывает различные множители строки

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

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

Пусть u — (возможно, бесконечная) последовательность символов из алфавита. Определим функцию p u ( n ) положительного целого числа n как количество различных множителей (последовательных подстрок) длины n из строки  u . [1] [2] [3] [4] [5]

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

1 ≤ п ты ( н ) ≤ к н   , {\displaystyle 1\leq p_{u}(n)\leq k^{n}\ ,}

границы достигаются постоянным словом и дизъюнктивным словом , [6] например, словом Чамперноуна соответственно. [7] Для бесконечных слов u мы имеем p u ( n ) ограниченное, если u в конечном счете периодично (конечная, возможно пустая, последовательность, за которой следует конечный цикл). Наоборот, если p u ( n ) ≤ n для некоторого n , то u в конечном счете периодично. [3] [8]

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

Набор S конечных двоичных слов сбалансирован , если для каждого n подмножество S n слов длины n обладает свойством, что вес Хэмминга слов в S n принимает не более двух различных значений. Сбалансированная последовательность — это та, для которой сбалансирован набор факторов. [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] а ( б б ) ∗ а {\displaystyle а(бб)^{*}а}

Л ⊆ { х у к з : х , у , з ∈ Ф ,   к ∈ Н }   . {\displaystyle L\subseteq \{xy^{k}z:x,y,z\in F,\ k\in \mathbb {N} \}\ .}

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

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

ЧАС т о п ( ты ) = лим н → ∞ бревно ⁡ п ты ( н ) н бревно ⁡ к   . {\displaystyle H_{\mathrm {top} }(u)=\lim _{n\rightarrow \infty }{\frac {\log p_{u}(n)}{n\log k}}\ .}

Предел существует, поскольку логарифм функции сложности является субаддитивным . [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 n (что следовало бы, если бы все такие числа были нормальными ), но все, что известно в этом случае, — это то, что p растет быстрее, чем любая линейная функция от n . [25]

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

Ссылки

  1. ^ Лотер (2011) стр.7
  2. ^ ab Лотер (2011) стр.46
  3. ^ ab Pytheas Fogg (2002) стр.3
  4. ^ Берстель и др. (2009) стр.82
  5. ^ Аллуш и Шалит (2003) стр.298
  6. ^ ab Bugeaud (2012) стр.91
  7. ^ Кассень и Николя (2010) стр.165
  8. ^ Аллуш и Шалит (2003) стр.302
  9. ^ abc Берте и Риго (2010) стр.166
  10. ^ Кассень и Николя (2010) стр.166
  11. ^ Лотер (2011) стр.22
  12. ^ Аллуш и Шалит (2003) стр.313
  13. ^ Лотер (2011) стр.48
  14. ^ abc Пифей Фогг (2002) стр.6
  15. ^ Аллуш и Шалит (2003) стр.318
  16. ^ de Luca, Aldo (1995). "Свойство деления слова Фибоначчи". Information Processing Letters . 54 (6): 307–312. doi :10.1016/0020-0190(95)00067-M.
  17. ^ Пифей Фогг (2002) стр.368
  18. ^ Берстель и др. (2009) стр.84
  19. ^ Берте и Риго (2010) стр.136
  20. ^ Пифей Фогг (2002) стр.4
  21. ^ Аллуш и Шалит (2003) стр.303
  22. ^ Кассень и Николя (2010) стр.169
  23. ^ Берте и Риго (2010) стр.391
  24. ^ Берте и Риго (2010) стр.169
  25. ^ Берте и Риго (2010) стр.414
  26. ^ Бланше-Садри, Франсин; Фокс, Натан (2013). «Об асимптотической абелевой сложности морфических слов». В Беаль, Мари-Пьер; Картон, Оливье (ред.). Развитие теории языка. Труды 17-й Международной конференции, DLT 2013, Марн-ла-Валле, Франция, 18–21 июня 2013 г. Конспект лекций по информатике. Том 7907. Берлин, Гейдельберг: Springer-Verlag . С. 94–105. doi :10.1007/978-3-642-38771-5_10. ISBN 978-3-642-38770-8. ISSN  0302-9743.
  • Allouche, Jean-Paul; Shallit, Jeffrey (2003). Автоматические последовательности: теория, приложения, обобщения . Cambridge University Press . ISBN 978-0-521-82332-6. Збл  1086.11015.
  • Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Комбинаторика слов. Слова Кристоффеля и повторения в словах. Серия монографий CRM. Том 27. Providence, RI: Американское математическое общество . ISBN 978-0-8218-4480-9. Збл  1161.68043.
  • Берте, Валери ; Риго, Мишель, ред. (2010). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том 135. Кембридж: Cambridge University Press . ISBN 978-0-521-51597-9. Збл  1197.68006.
  • Бюжо, Янн (2012). Распределение по модулю один и диофантовы приближения . Cambridge Tracts in Mathematics. Том 193. Кембридж: Cambridge University Press . ISBN 978-0-521-11169-0. Збл  1260.11001.
  • Кассень, Жюльен; Николя, Франсуа (2010). «Факторная сложность». В Берте, Валери ; Риго, Мишель (ред.). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Т. 135. Кембридж: Cambridge University Press . С. 163–247. ISBN 978-0-521-51597-9. Збл  1216.68204.
  • Лотер, М. (2011). Алгебраическая комбинаторика слов . Энциклопедия математики и ее приложений. Т. 90. С предисловием Жана Берстеля и Доминика Перрена (Переиздание издания 2002 года в твердом переплете). Cambridge University Press. ISBN 978-0-521-18071-9. Збл  1221.68183.
  • Пифей Фогг, Н. (2002). Берте, Валери ; Ференци, Себастьен; Модуит, Кристиан; Сигел, А. (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN 3-540-44141-7. Збл  1014.11015.
Взято с "https://en.wikipedia.org/w/index.php?title=Сложность_функции&oldid=1134863590"