|
СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ
АННОТАЦИИ
Кассень Ж., Петров Ф. В., Фрид А. Э. О возможных скоростях роста языков Тëплица //
Том 52 (2011), Номер 1,
стр. 8194
Рассматривается новое семейство факторных языков, комбинаторная сложность которых растет как $\Theta(n^{\alpha})$, где $\alpha$ --- корень некоторого трансцендентного уравнения. Асимптотический рост функции сложности исследуется с применением аналитических методов, в частности, следствия из теоремы Винера~--- Питта. Рассматриваемые факторные языки являются языками арифметических подслов бесконечных слов; таким образом, описывается новое семейство бесконечных слов с необычным ростом арифметической сложности.
|
|
© Сибирский Математический Журнал, 2003-2006
|
|