EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Complexity functions of infinite sequences

Be'eri Greenfeld, Paul-Henry Leemann, Carlos Gustavo Moreira, Efim Zelmanov

Proceedings of the National Academy of Sciences · 03.11.2026 · 123 (44)

DOI: 10.1073/pnas.2627766123 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the National Academy of Sciences, online erschienen am 29.10.2026. Verfasst von Be'eri Greenfeld und 3 weiteren Autor:innen. Beteiligte Einrichtung: Department of Mathematics and Statistics, Hunter College, City University of New York, New York, NY 10065. Die Arbeit nennt 52 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Xi'an Jiaotong-Liverpool University (XJTLU), Data Center of Management Science, National Natural Science Foundation of China - Peking University (DCMS, NSFC-PKU), | National Natural Science Foundation of China-Guangdong Joint Fund (-).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We address the inverse problem for complexity functions of infinite words, which asks which functions can occur as complexity functions of infinite words. We survey our recent advances on this problem and several of its ramifications. We describe an asymptotic solution to the inverse problem, realizing every function satisfying two necessary conditions as the complexity function of an infinite word up to asymptotic equivalence. We then turn to phenomena beyond asymptotic equivalence, presenting constructions of infinite words with seemingly contradictory behavior of the discrete derivatives of their complexity functions. These lead to a solution of a 1995 problem of Cassaigne and to applications in symbolic dynamics, including the question of convergence of Rauzy graphs, as well as to the growth and asymptotic invariants of algebraic structures.

Schlagwörter

Stichwörter der Autor:innen

combinatorics on wordsgrowth of algebraic structuressubword complexitysymbolic dynamics

Autor:innen und Institutionen

  • Department of Mathematics and Statistics, Hunter College, City University of New York, New York, NY 10065.
  • Department of Pure Mathematics, Xi'an Jiaotong-Liverpool University, Suzhou, Jiangsu 215123, China.
  • Southern University of Science and Technology International Center for Mathematics, Shenzhen, Guangdong 518055, China.
  • Instituto Nacional de Matemática Pura e Aplicada, Rio de Janeiro, RJ 22460-320, Brazil.

Förderung

  • Xi'an Jiaotong-Liverpool University (XJTLU)
  • Data Center of Management Science, National Natural Science Foundation of China - Peking University (DCMS, NSFC-PKU)
  • | National Natural Science Foundation of China-Guangdong Joint Fund (-)
  • 广东省人民政府 | National Natural Science Foundation of China-Guangdong Joint Fund

Zitieren

APA

Greenfeld, B., Leemann, P. H., Moreira, C. G., & Zelmanov, E. (2026). Complexity functions of infinite sequences. Proceedings of the National Academy of Sciences, 123(44). https://doi.org/10.1073/pnas.2627766123

Vancouver

Greenfeld B, Leemann PH, Moreira CG, Zelmanov E. Complexity functions of infinite sequences. Proceedings of the National Academy of Sciences. 2026;123(44). doi:10.1073/pnas.2627766123

BibTeX
@article{Greenfeld2026,
  author = {Greenfeld, Be'eri and Leemann, Paul-Henry and Moreira, Carlos Gustavo and Zelmanov, Efim},
  title = {Complexity functions of infinite sequences},
  journal = {Proceedings of the National Academy of Sciences},
  year = {2026},
  volume = {123},
  number = {44},
  doi = {10.1073/pnas.2627766123}
}
Kostenlos starten →