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/

[1] Banks W. D., Conflitti A., Shparlinski I. E., “Character sums over integers with restricted $g$-ary digits”, Illinois J. Math., 46:3 (2002), 819–836 | DOI | MR | Zbl

[2] Avgustinovich S., Cassaigne J., Frid A., “Sequences of low arithmetical complexity”, Theoret. Inform. Appl., 40 (2006), 569–582 | DOI | MR | Zbl

[3] Allouche J.-P., Baake M., Cassaigne J., Damanik D., “Palindrome complexity Selected papers in honor of Jean Berstel”, Theoret. Comput. Sci., 292:1 (2003), 9–31 | DOI | MR | Zbl

[4] Avgustinovich S. V., Fon-Der-Flaass D. G., Frid A. E., “Arithmetical complexity of infnite words”, Proc. Words, Languages and Combinatorics III (2000), World Scientifc, Singapore, 2003, 51–62 | DOI | MR

[5] Berstel J., “P. Seebold. Sturmian words”, Algebraic Combinatorics on Words, ed. M. Lothaire, Cambridge University Press, 2002, 40–97 | MR

[6] Berstel J., M. Pocchiola, “A geometric proof of the enumeration formula for Sturmian words”, Int. J. Algebra and Comput., 3 (1993), 349–355 | DOI | MR | Zbl

[7] Bell J. P., Shallit J., “Lie complexity of words”, Theoret. Comput. Sci., 2022 (to appear) | MR

[8] Brown C., “A characterization of the quadratic irrationals”, Canad. Math. Bull., 36:4 (1991) | MR | Zbl

[9] Bresenham J. E., “Algorithm for computer control of a digital plotter”, IBM Systems J., 1965, 25–30 | DOI

[10] Cassaigne J., E.A. Frid, “On the arithmetical complexity of Sturmian words”, Theoretical Computer Science, 380 (2007), 304–316 | DOI | MR | Zbl

[11] Cassaigne J., Fici G., Sciortino M., Zamboni L., “Cyclic complexity of words”, J. Combin. Theory Ser. A, 145 (2017), 36–56 | DOI | MR | Zbl

[12] Cassaigne J., Richomme G., Saari K., Zamboni L., “Avoiding. Abelian powers in binary words with bounded Abelian complexity”, Internat. J. Found. Comput. Sci., 22 (2011), 905–920 | DOI | MR | Zbl

[13] Cassaigne J., Kaborée I., Tapsoba T., “On a new notion of complexity on infinite words”, Acta Univ. Sapientiae Math., 2:2 (2010), 127–136 | MR | Zbl

[14] Ethan M. Coven, Hedlund G., “Sequences with minimal block growth”, Mathematical systems theory, 7 (1973), 138–153 | DOI | MR | Zbl

[15] Dulucq S., D. Gouyou-Beauchamp, Sur les facteurs des suites de Sturm, Rapport No. I-8735, Comput. Sci., 1987

[16] A. Frid, “Sequences of linear arithmetical complexity”, Theoret. Comput. Sci., 339 (2005), 68–87 | DOI | MR | Zbl

[17] A. Frid, “A lower bound for the arithmetical complexity of Sturmian words”, Siberian Electron. Math. Rep., no. 2, 14–22 (in Russian, English abstract) | MR | Zbl

[18] Fraenkel A.S., M. Mushkin, U. Tassa, “Determination of by $[n\theta]$ its sequence of differences”, Canad. Math. Bull., 1978, 441–446 | DOI | MR | Zbl

[19] Kamae T., Zamboni L., “Sequence entropy and the maximal pattern complexity of infinite words”, Ergodic Theory and Dynamical Systems, 22:4 (2002), 1191–1199 | MR | Zbl

[20] Karhumaki J., Saarela A., Zamboni L. Q., “On a generalization of abelian equivalence and complexity of infinite words”, J. Combin. Theory, Ser. A, 120:8 (2013), 2189–2206 | DOI | MR | Zbl

[21] Hedlund G.A., M. Morse, “Symbolic dynamics”, Amer. J. Math., 1938, 815–866 | MR | Zbl

[22] Hedlund G.A., M. Morse, “Sturmian sequences”, Amer. J. Math., 1940 | MR

[23] Hedlund G.A., “Sturmian minimal sets”, Amer. J. Math., 1944, 605–620 | DOI | MR | Zbl

[24] Ito S., Yasutomi S., “On continued fractions, substitutions and characteristic sequences”, Japan. J. Math., 1990, 287–306 | DOI | MR | Zbl

[25] Leibman A., Bergelson V., “Polynomial extensions of van der Waerden's and Szemeredi's theorems”, Journal of the American Math Society, 9 (1996), 725–753 | DOI | MR | Zbl

[26] Mignosi F., “On the number of factors of Sturmian words”, Theoret. Comput. Sci., 1991, 71–84 | DOI | MR | Zbl

[27] Mignosi F., and Restivo A., “A new complexity function for words based on periodicity”, Int. J. Algebra Comput., 23:4 (2013), 963–988 | DOI | MR

[28] Queffelec M., Substitution Dynamical Systems, Spectral Analysis Lecture Notes Math., 1294, Springer-Verlag, 1987 | DOI | MR | Zbl

[29] Rauzy G., “Suites a termes dans un alphabet fini”, Semin. Theorie des Nombres, 1982–1983, Bordeaux, 25-01–25-16 | MR

[30] Rauzy G., “Mots infinis en arithmetique”, Automata on infinite words, Lect. Notes Comp. Sci., ed. D. Perrin, 1985, 165–171 | MR | Zbl

[31] Rauzy G., “Sequences defined by iterated morphisms”, Workshop on Sequences, Lecture Notes Comput. Sci., ed. R. Capocelli (to appear) | MR

[32] Rigo M., Salimov P., “Another generalization of abelian equivalence: Binomial complexity of infinite words”, Theoret. Comput. Sci., 601 (2015), 47–57 | DOI | MR | Zbl

[33] Seebold P., “Fibonacci morphisms and Sturmian words”, Theoret. Comput. Sci., 1991, 367–384 | MR

[34] Series C., “The geometry of Marhoff numbers”, The Mathematical Intelligencer, 1985, 20–29 | DOI | MR | Zbl

[35] Stolarsky K., “Beatty sequences, continued fractions, and certain shift operators”, Cand. Math. Bull., 1976, 473–482 | DOI | MR | Zbl

[36] Szemeredi E., “On sets of integers containing no k elements in arithmetic progression”, Acta Arithm., 27 (1975), 199–245 | DOI | MR | Zbl

[37] E. Szemeredi, Regular partitions of graphs, Computer science department, School of Humanities and Sciences, Stanford University, 1975

[38] Thue A., “Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen”, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania, 1912

[39] Thue A., “Uber unendliche Zeichenreihen”, Norske Vid. Skrifter I Mat. Nat. Kl., Christiania, 7 (1906), 1–22; 10, 1–67

[40] Venkov A., Elementary Number Theory, Wolter-Noordho, Groningen, 1970 | MR | Zbl

[41] Van der Waerden B.L., “Beweis einer Baudetschen Vermutung”, Nieuw Arch. Wisk, 15 (1927), 212–216

[42] Russian Math. Surveys, 61:6 (2006), 1101–1166 | DOI | DOI | MR | Zbl