PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

On the character of words of sublinear complexity

Volume 184 / 2018

Luca Q. Zamboni Acta Arithmetica 184 (2018), 201-213 MSC: Primary 68R15. DOI: 10.4064/aa8577-3-2018 Published online: 27 July 2018


Let $\mathbb A^*$ denote the free monoid generated by a finite non-empty set $\mathbb A$. For each infinite word $x=x_0x_1x_2\cdots \in\mathbb A^\omega$, the factor complexity $p_x(n)$ counts the number of distinct blocks $x_ix_{i+1}\cdots x_{i+n-1}$ of length $n$ occurring in $x$. In other words, the factor complexity of $x$ is the complexity of the language of its factors $\operatorname{Fac}_x=\{x_ix_{i+1}\cdots x_{j}: 0\leq i\leq j\}$. Our starting point in this paper is the following characterisation of infinite words of sublinear factor complexity obtained recently by the author together with J. Cassaigne, A. Frid and S. Puzynina: Let $x\in \mathbb A^\omega$. Then $p_x(n)=O(n)$ if and only if $\operatorname{Fac}_{x} \subseteq S^2$ for some $S\subseteq \mathbb A^*$ with $\limsup p_S(n) \lt \infty$. In other words, $p_x(n)\leq Cn$ for some constant $C$ if and only if there exists a set $S$ of bounded complexity such that every factor $w$ of $x$ can be factored as $w=uv$ with $u,v \in S$. Given an infinite word $x\in \mathbb A^\omega$, we define its character, denoted $\chi(x)$, to be the least value of $\limsup p_S(n)$ over all languages $S$ such that $\operatorname{Fac}_x\subseteq S^2$. Clearly $\chi(x) \in [1, \infty]$, and it follows from the above characterisation that $p_x(n)=O(n)$ if and only if $\chi(x) \lt \infty$. We prove that $\chi(x)=1$ if and only if $x$ is ultimately periodic, and that $\chi(x)=2$ whenever $x$ is a Sturmian word.


  • Luca Q. ZamboniUniversité de Lyon
    Université Lyon 1, CNRS UMR 5208
    Institut Camille Jordan
    43 boulevard du 11 novembre 1918
    F69622 Villeurbanne Cedex, France

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image