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