# Wydawnictwa / Czasopisma IMPAN / Acta Arithmetica / Wszystkie zeszyty

## Acta Arithmetica

Artykuły w formacie PDF dostępne są dla subskrybentów, którzy zapłacili za dostęp online, po podpisaniu licencji Licencja użytkownika instytucjonalnego. Czasopisma do 2009 są ogólnodostępne (bezpłatnie).

## On the character of words of sublinear complexity

### Tom 184 / 2018

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

#### Streszczenie

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.

#### Autorzy

• 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

## Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Odśwież obrazek