A+ CATEGORY SCIENTIFIC UNIT

# Publishing house / Journals and Serials / Acta Arithmetica / All issues

## Acta Arithmetica

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

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

#### Abstract

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.

#### Authors

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

## Search for IMPAN publications

Query phrase too short. Type at least 4 characters.