RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2011 Volume 52, Number 1, Pages 81–94 (Mi smj2179)

On possible growths of Toeplitz languages

J. Cassaignea, F. V. Petrovb, A. E. Fridc

a Institut de Mathématiques de Luminy, Marseille Cedex, France
b St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg
c Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Abstract: We consider a new family of factorial languages whose subword complexity grows as $\Theta(n^\alpha)$, where $\alpha$ 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.

Keywords: subword complexity, arithmetical complexity, combinatorics on words, Toeplitz words, asymptotic combinatorics, analytical methods in combinatorics, Tauberian theorems, Wiener–Pitt theorem.

UDC: 519.115.8

Received: 10.03.2010


 English version:
Siberian Mathematical Journal, 2011, 52:1, 63–73

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025