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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Article Journal Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]