Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
О возможных скоростях роста языков Тёплица. / Кассень, Ж.; Петров, Ф. В.; Фрид, А. Э.
в: СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ, Том 52, № 1, 2011, стр. 81-94.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - О возможных скоростях роста языков Тёплица
AU - Кассень, Ж.
AU - Петров, Ф. В.
AU - Фрид, А. Э.
PY - 2011
Y1 - 2011
N2 - Рассматривается новое семейство факторных языков, комбинаторная сложность которых растет как $\Theta(n^a)$, где $a$ – корень некоторого трансцендентного уравнения. Асимптотический рост функции сложности исследуется с применением аналитических методов, в частности, следствия из теоремы Винера–Питта. Рассматриваемые факторные языки являются языками арифметических подслов бесконечных слов; таким образом, описывается новое семейство бесконечных слов с необычным ростом арифметической сложности.
AB - Рассматривается новое семейство факторных языков, комбинаторная сложность которых растет как $\Theta(n^a)$, где $a$ – корень некоторого трансцендентного уравнения. Асимптотический рост функции сложности исследуется с применением аналитических методов, в частности, следствия из теоремы Винера–Питта. Рассматриваемые факторные языки являются языками арифметических подслов бесконечных слов; таким образом, описывается новое семейство бесконечных слов с необычным ростом арифметической сложности.
KW - комбинаторная сложность
KW - арифметическая сложность
KW - слова Тёплица
KW - аналитические методы в комбинаторике
KW - тауберовы теоремы
M3 - статья
VL - 52
SP - 81
EP - 94
JO - СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ
JF - СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ
SN - 0037-4474
IS - 1
ER -
ID: 5463538