EUVIMEDEUVIMED entdecken
Crossref

On the complexity of subshifts and infinite words

Be’eri Greenfeld, Carlos Gustavo Moreira, Efim Zelmanov

Journal of the European Mathematical Society · 05.01.2026

DOI: 10.4171/jems/1753 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the European Mathematical Society, erschienen am 05.01.2026. Verfasst von Be’eri Greenfeld und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We characterize the complexity functions of subshifts up to asymptotic equivalence. The complexity function of every aperiodic subshift is non-decreasing, submultiplicative and grows at least linearly. We prove that, conversely, every function satisfying these conditions is asymptotically equivalent to the complexity function of a recurrent subshift, equivalently, a recurrent infinite word. Our construction is explicit, algorithmic in nature and is philosophically based on constructing certain ‘Cantor sets of integers’, whose ‘gaps’ correspond to blocks of zeros. We also prove that every non-decreasing submultiplicative function is asymptotically equivalent, up to a linear error term, to the complexity function of a minimal subshift.

Zitieren

APA

Greenfeld, B., Moreira, C. G., & Zelmanov, E. (2026). On the complexity of subshifts and infinite words. Journal of the European Mathematical Society. https://doi.org/10.4171/jems/1753

Vancouver

Greenfeld B, Moreira CG, Zelmanov E. On the complexity of subshifts and infinite words. Journal of the European Mathematical Society. 2026. doi:10.4171/jems/1753

BibTeX
@article{Greenfeld2026,
  author = {Greenfeld, Be’eri and Moreira, Carlos Gustavo and Zelmanov, Efim},
  title = {On the complexity of subshifts and infinite words},
  journal = {Journal of the European Mathematical Society},
  year = {2026},
  doi = {10.4171/jems/1753}
}
Kostenlos starten →