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

Luca Q. Zamboni 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.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek