Geodesic
On the complexity functions of Sturmian words
Čebyševskij sbornik, Tome 24 (2023) no. 4, pp. 63-77

Voir la notice de l'article provenant de la source Math-Net.Ru

The key issue of the paper is combinatorial complexity functions of infinite words, especially factor complexity and its modifications. First of all, we present an overview of the available results for the class of words with the minimal factor complexity - Sturmian words. Special attention is paid to the arithmetical complexity of infinite words, the study of which was initiated by Van der Waarden Theorem on one-color arithmetic progressions. Arithmetical complexity is presented in a sense a modification of factor complexity. An overview of current results and exact values of arithmetic complexity for Sturmian words is presented. We present polynomial Van der Waerden Theorem, which gives rise to the study of a more generalized modification of the factor complexity function - the polynomial complexity of infinite words. In conclusion, we present open problems for further research.
Keywords: Sturmian word, factor complexity, arithmetical complexity, polynomial complexity. 
@article{CHEB_2023_24_4_a5,
     author = {V. O. Kirova and I. V. Godunov},
     title = {On the complexity functions of {Sturmian} words},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {63--77},
     publisher = {mathdoc},
     volume = {24},
     number = {4},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2023_24_4_a5/}
}
TY  - JOUR
AU  - V. O. Kirova
AU  - I. V. Godunov
TI  - On the complexity functions of Sturmian words
JO  - Čebyševskij sbornik
PY  - 2023
SP  - 63
EP  - 77
VL  - 24
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2023_24_4_a5/
LA  - ru
ID  - CHEB_2023_24_4_a5
ER  - 
%0 Journal Article
%A V. O. Kirova
%A I. V. Godunov
%T On the complexity functions of Sturmian words
%J Čebyševskij sbornik
%D 2023
%P 63-77
%V 24
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2023_24_4_a5/
%G ru
%F CHEB_2023_24_4_a5
V. O. Kirova; I. V. Godunov. On the complexity functions of Sturmian words. Čebyševskij sbornik, Tome 24 (2023) no. 4, pp. 63-77. http://geodesic.mathdoc.fr/item/CHEB_2023_24_4_a5/