On the complexity functions of Sturmian words
https://doi.org/10.22405/2226-8383-2023-24-4-63-77
Abstract
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.
About the Authors
Valeria Orlanovna KirovaRussian Federation
Igor Valentinovich Godunov
Russian Federation
References
1. Banks, W. D., Conflitti, A. & Shparlinski, I. E. 2002, “Character sums over integers with
2. restricted 𝑔-ary digits”, Illinois J. Math., vol. 46, no. 3, pp. 819-836.
3. Avgustinovich S., Cassaigne J., Frid A. E. 2006, “Sequences of low arithmetical complexity”
4. Theoret. Inform. Appl. vol.40, pp. 569–582.
5. Allouche J.-P. Baake M. Cassaigne J., Damanik D. E. 2003, “Palindrome complexity Selected
6. papers in honor of Jean Berstel” Theoret. Comput. Sci. vol. 292, no. 1, pp. 9–31.
7. Avgustinovich S. V. , Fon-Der-Flaass D. G. , Frid A. E. E.2003 “Arithmetical complexity of
8. infnite words” Proc. Words, Languages and Combinatorics III, Singapore: World Scientifc, pp.
9. -62.
10. Berstel J., P. Seebold. E.2002 “Sturmian words, in: M. Lothaire, Algebraic Combinatorics on
11. Words”, Cambridge University Press, pp. 40-97.
12. Berstel J., M. Pocchiola. E.1993 “A geometric proof of the enumeration formula for Sturmian
13. words”, Int. J. Algebra and Comput., vol 3, pp. 349 -355.
14. Bell, J. P., Shallit, J. E. 2022 “Lie complexity of words”, Theoret. Comput. Sci. in press.
15. Brown C. E.1991 “A characterization of the quadratic irrationals”, Canad. Math. Bull., vol.36.
16. Bresenham J. E. E.1965 “Algorithm for computer control of a digital plotter.”, IBM Systems
17. pp. 25-30.
18. Cassaigne J., E.A. Frid. E. 2007 “On the arithmetical complexity of Sturmian words”,
19. Theoretical Computer Science, vol. 380, pp.304-316.
20. Cassaigne J., Fici, G., Sciortino, M., Zamboni, L. E.2017 “Cyclic complexity of words”, J.
21. Combin. Theory Ser. , vol. 145 , pp. 36–56.
22. Cassaigne J., Richomme, G., Saari, K., Zamboni, L. Avoiding. E.2011 “Abelian powers in binary words with bounded Abelian complexity”, Internat J. Found. Comput. Sci. vol.22, no. 4, pp.905–920.
23. Cassaigne J., Kabor´e, I., Tapsoba, T. E.2010 “On a new notion of complexity on infinite
24. words.”, Acta Univ. Sapientiae Math. vol. 2, no. 2 , pp. 127–136.
25. Ethan M. Coven, Hedlund G. E.1973 “ Sequences with minimal block growth”, Mathematical
26. systems theory vol. 7, pp. 138–153.
27. Dulucq S., D. Gouyou-Beauchamp. E.1987 “ Sur les facteurs des suites de Sturm”, Rapport No. I-8735, Comput. Sci.
28. A. Frid. E.2005 “Sequences of linear arithmetical complexity”, Theoret. Comput. Sci. vol. 339,
29. pp. 68–87.
30. A. Frid “A lower bound for the arithmetical complexity of Sturmian words”, Siberian Electron.
31. Math. Rep. 2, pp. 14–22.
32. Fraenkel A.S., M. Mushkin, U. Tassa. E. 1978 “Determination of by [𝑛𝜃] its sequence of
33. differences”, Canad. Math. Bull. , pp. 441-446.
34. Kamae, T., and Zamboni, L. E. 2002 “Sequence entropy and the maximal pattern complexity
35. of infinite words”, Ergodic Theory and Dynamical Systems vol.22, no.4, pp. 1191–1199.
36. Karhumaki, J., Saarela, A., and Zamboni, L. Q. E. 2013, “On a generalization of abelian
37. equivalence and complexity of infinite words”, J. Combin. Theory, Ser. A 120, no.8, pp.
38. –2206.
39. Hedlund G.A. , M. Morse. E.1978, “Symbolic dynamics”, Amer. J. Math, pp. 815-866.
40. Hedlund G.A., M. Morse. E.1940 “Sturmian sequences”, Amer. J. Math.
41. Hedlund G.A. E.1944 “Sturmian minimal sets”, Amer. J. Math, pp. 605-620.
42. Ito S., Yasutomi S. E.1990, “On continued fractions, substitutions and characteristic sequences”, Japan. J. Math., pp. 287-306.
43. Leibman A., Bergelson V. “ Polynomial extensions of van der Waerden’s and Szemeredi’s
44. theorems ”, Journal of the American Math Society, Vol. 9, 1996, pp. 725-753.
45. Mignosi F. E.1991, “On the number of factors of Sturmian words”, Theoret. Comput. Sci. pp.
46. -84.
47. Mignosi, F., and Restivo, A. E.2013, “A new complexity function for words based on
48. periodicity”, Int. J. Algebra Comput. vol.23, no.4, pp. 963–988.
49. Queffelec M. E.1987, “Substitution Dynamical Systems”, Spectral Analysis Lecture Notes Math., vol. 1294, Springer-Verlag.
50. Rauzy G. E.1982-1983, “Suites a termes dans un alphabet fini, Semin”, Theorie des Nombres, 25-01,25-16, Bordeaux.
51. Rauzy G. E.1985, “Mots infinis en arithmetique, in :Automata on infinite words (D. Perrin
52. ed.)”, Lect. Notes Comp. Sci. pp. 165-171.
53. Rauzy G. “Sequences defined by iterated morphisms, in :Workshop on Sequences (R. Capocelli ed.)”, Lecture Notes Comput. Sci., to appear.
54. Rigo M. and Salimov, P. E. 2015, “Another generalization of abelian equivalence: Binomial
55. complexity of infinite words”, Theoret. Comput. Sci. no.601, pp. 47–57.
56. Seebold P. E.1991, “Fibonacci morphisms and Sturmian words”, Theoret. Comput. Sci. ,
57. pp.367-384.
58. Series C. E.1985, “The geometry of Marhoff numbers”, The Mathematical Intelligencer , pp.
59. -29.
60. Stolarsky K. E.1976 “Beatty sequences, continued fractions, and certain shift operators”, Cand. Math. Bull. , pp. 473-482.
61. Szemeredi E. E.1975 “On sets of integers containing no k elements in arithmetic progression”, Acta Arithm. . vol. 27, pp. 199-245.
62. E. Szemeredi “Regular partitions of graphs”, Computer science department, School of Humanities and Sciences, Stanford University, 1975
63. Thue A. E.1912 “Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen”, Norske
64. Vid. Skrifter I Mat.-Nat. Kl., Christiania.
65. Thue A. E.1906, “Uber unendliche Zeichenreihen ”, Norske Vid. Skrifter I Mat. Nat. Kl.,
66. Christiania. vol. 7 pp. 1-22., vol. 10., pp. 1-67.
67. Venkov A. E.1970, “Elementary Number Theory”, Wolter-Noordho, Groningen.
68. Van der Waerden B.L, “Beweis einer Baudetschen Vermutung”, Nieuw Arch. Wisk., 15 (1927),pp. 212–216.
69. Shkredov I. D. 2006, “Semeredi’s theorem and problems of arithmetic progressions”, Achievements of mathematical sciences, 61:6(372), 111–178; Russian Math. Surveys, 61:6, pp.
70. –1166.
Review
For citations:
Kirova V.O., Godunov I.V. On the complexity functions of Sturmian words. Chebyshevskii Sbornik. 2023;24(4):63-77. (In Russ.) https://doi.org/10.22405/2226-8383-2023-24-4-63-77