Кассень Ж., Петров Ф. В., Фрид А. Э.
О возможных скоростях роста языков Тёплица

Рассматривается новое семейство факторных языков, комбинаторная сложность которых растет как Θ(n^α), где α — корень некоторого трансцендентного уравнения. Асимптотический рост функции сложности исследуется с применением аналитических методов, в частности, следствия из теоремы Винера — Питта. Рассматриваемые факторные языки являются языками арифметических подслов бесконечных слов; таким образом, описывается новое семейство бесконечных слов с необычным ростом арифметической сложности.

Cassaigne J., Frid A. E., Petrov F. V.
On possible growths of Toeplitz languages

We consider a new family of factorial languages whose subword complexity grows as Θ(n^α), where α is the only positive root of some transcendental equation. The asymptotic growth of the complexity function of these languages is studied by discrete and analytical methods, a corollary of the Wiener-Pitt theorem inclusive. The factorial languages considered are also languages of arithmetical factors of infinite words; so, we describe a new family of infinite words with an unusual growth of arithmetical complexity.

Полный текст статьи / Full texts:

• PDF file
• PostScript file