Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

# Simple Search

Query:
Enter a query and click »Search«...
Format:
Display: entries per page entries
Zbl 1155.68479
Nakashima, Izumi; Tamura, Jun-ichi; Yasutomi, Shin-ichi
*-Sturmian words and complexity.
(English)
[J] J. ThÃ©or. Nombres Bordx. 15, No. 3, 767-804 (2003). ISSN 1246-7405

Given an infinite sequence, the complexity function $p(n,w)$ counts the number of different subwords of $w$ with size $n$. Since Hedlund and Morse, it is known that when one considers a binary sequence, the sequence is ultimately periodic if and only if $p(n,w) \leq n$ for a given $n$. Non-periodic sequences with the lowest complexity satisfy $p(n,w)=n+1$ for every $n$; they are called Sturmian sequences. They have zero entropy and correspond to the discrete coding of lines with irrational slope in ${\mathbb R}^2$. \par In this paper, the authors introduce a new complexity function $p_{\star}(n,w)$ which counts the number of different subwords of $w$ that appear infinitely often in $w$. Then, $p_{\star}(n,w) \leq p(n,w)$, with equality when $w$ is a Sturmian sequence for instance. The authors define ${\star}$-Sturmian sequences to be infinite words $w$ satisfying $\vert \vert A\vert _1 - \vert B\vert _1\vert \leq 1$ for any subword $A$, $B$ having the same size and appearing infinitely often in $w$. They prove that this is equivalent with $p_{\star}(n,w) \leq n+1$ for any $n$. Moreover, such sequences are either Sturmian or codings of lines with rational slopes. A class of examples with explicit complexity is described. In general, such sequences can have a large complexity (examples are given with $p(n,w) \geq 2^{n^{1-\varepsilon}}$) but they always have a zero entropy.
[Anne Siegel (Rennes)]
MSC 2000:
*68R15 Combinatorics on words
05A05 Combinatorial choice problems
37B10 Symbolic dynamics

Keywords: Sturmian words; complexity; approximation of rational lines; infinite occurrences

Highlights
Master Server