Jump to content

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

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

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

[ редактировать ]

Пусть 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]

  1. ^ Лотарь (2011) стр.7
  2. ^ Jump up to: а б Лотарь (2011) стр.46
  3. ^ Jump up to: а б Пифей Фогг (2002) стр.3
  4. ^ Берстель и др. (2009) стр.82
  5. ^ Аллуш и Шалит (2003) стр.298
  6. ^ Jump up to: а б Бюжо (2012) стр.91
  7. ^ Кассень и Николя (2010) стр.165
  8. ^ Аллуш и Шалит (2003) стр.302
  9. ^ Jump up to: а б с Берте и Риго (2010) стр.166
  10. ^ Кассень и Николя (2010) стр.166
  11. ^ Лотарь (2011) стр.22
  12. ^ Аллуш и Шалит (2003) стр.313
  13. ^ Лотарь (2011) стр.48
  14. ^ Jump up to: а б с Пифей Фогг (2002) стр.6
  15. ^ Аллуш и Шалит (2003) стр.318
  16. ^ де Лука, Альдо (1995). «Свойство деления слова Фибоначчи». Письма об обработке информации . 54 (6): 307–312. дои : 10.1016/0020-0190(95)00067-М .
  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. дои : 10.1007/978-3-642-38771-5_10 . ISBN  978-3-642-38770-8 . ISSN   0302-9743 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 4cf88a8c28ca046f9998c31def636f1f__1674259020
URL1:https://arc.ask3.ru/arc/aa/4c/1f/4cf88a8c28ca046f9998c31def636f1f.html
Заголовок, (Title) документа по адресу, URL1:
Complexity function - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)