DOI

Комбинаторная сложность языка L определяется как функция p_L(n), которая считает для всякого n число различных слов в L длины n. Нас итересует следующий вопрос: верно ли, что L содержится в конечном произведении вида S^k, где S - язык сложности, меньшей, чем L. В статье рассматриваются языка нулевой топологической энтропии, а именно lim sup_{n→∞} log p_L(n)/n = 0. Мы определяем α-размерность языка L как минимум целых чисел k, таких что существует язык S сложности O(n^α), такой что L ⊆ S^k. Стоимостью c(L) языка L называется минимум действительных чисел α, для которых α-размерность языка L конечна. В частности, определения можно использовать для языка всех факторов бесконечного слова. В статье изучаются связи между сложностью языка (или бесконечного слова) и его размерностью и стоимостью, и показано, что эти связи имеют довольно сложную и неочевидную природу.
Язык оригиналаанглийский
Страницы (с-по)639-660
Число страниц22
ЖурналBulletin de la Societe Mathematique de France
Том147
Номер выпуска4
DOI
СостояниеОпубликовано - 2019

    Предметные области Scopus

  • Математика (все)

ID: 52532700