Complexity functions of infinite sequences
Related Experiment Video
Updated: Oct 31, 2026

Microstate and Omega Complexity Analyses of the Resting-state Electroencephalography
Published on: June 15, 2018
Be'eri Greenfeld1, Paul-Henry Leemann2, Carlos Gustavo Moreira3,4
1Department of Mathematics and Statistics, Hunter College, City University of New York, New York, NY 10065.
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 Concept Videos
Sequences
Introduction to Sequences
Introduction to Infinite Series
Geometric Sequences
Indeterminate Products
Convergence of Sequences

