Complexity functions of infinite sequences
4 affiliations
- 1Department of Mathematics and Statistics, Hunter College, City University of New York, New York, NY 10065
- 2Department of Pure Mathematics, Xi’an Jiaotong–Liverpool University, Suzhou, Jiangsu 215123, China
- 3Southern University of Science and Technology International Center for Mathematics, Shenzhen, Guangdong 518055, China
- 4Instituto Nacional de Matemática Pura e Aplicada, Rio de Janeiro, RJ 22460-320, Brazil
Abstract
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.
Related
- RNAGEN: A Generative Adversarial Network‐Based Model to Generate Synthetic RNA Sequences to Target Proteins
- Hantavirus species detection from viral genome sequences using explainable artificial intelligence techniques
- Automatic Generation of Novel Highly-Functional Molecular Sequences
- The chromosomal genome sequence of a shovel-head worm, Maea johnstoni (Fiege, Licher & Mackie, 2000) (Spionida: Magelonidae) and its associated microbial metagenome sequences.
- TargetMITO: a rule-based model for generating functional synthetic mitochondrial targeting sequences in yeast
BibTeX
@article{greenfeld2026complexity,
title = {{Complexity functions of infinite sequences}},
author = {Be’eri Greenfeld and Paul-Henry Leemann and Carlos Gustavo Moreira and Efim Zelmanov},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
year = {2026},
month = oct,
doi = {10.1073/pnas.2627766123},
url = {https://doi.org/10.1073/pnas.2627766123},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - JOUR
TI - Complexity functions of infinite sequences
AU - Be’eri Greenfeld
AU - Paul-Henry Leemann
AU - Carlos Gustavo Moreira
AU - Efim Zelmanov
PY - 2026
DA - 2026/10/29
JO - Proceedings of the National Academy of Sciences of the United States of America
DO - 10.1073/pnas.2627766123
UR - https://doi.org/10.1073/pnas.2627766123
AB - 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.
SN - 0027-8424
SN - 1091-6490
ER -