On low-complexity bi-infinite words and their factors

Alex Heinis

Displaying similar documents to “On low-complexity bi-infinite words and their factors”

*-sturmian words and complexity

Izumi Nakashima, Jun-Ichi Tamura, Shin-Ichi Yasutomi (2003)

Journal de théorie des nombres de Bordeaux

Similarity:

We give analogs of the complexity $p (n)$ and of Sturmian words which are called respectively the $*$ -complexity $p_{*} (n)$ and $*$ -Sturmian words. We show that the class of $*$ -Sturmian words coincides with the class of words satisfying $p_{*} (n) \leq n + 1$ , and we determine the structure of $*$ -Sturmian words. For a class of words satisfying $p_{*} (n) = n + 1$ , we give a general formula and an upper bound for $p (n)$ . Using this general formula, we give explicit formulae for $p (n)$ for some words belonging to this class. In general, $p (n)$ can take large...

Hereditary properties of words

József Balogh, Béla Bollobás (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Let $𝒫$ be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to $𝒫$ is also in $𝒫$ . Extending the classical Morse-Hedlund theorem, we show that either $𝒫$ contains at least $n + 1$ words of length $n$ for every $n$ or, for some $N$ , it contains at most $N$ words of length $n$ for every $n$ . More importantly, we prove the following quantitative extension of this result: if $𝒫$ has $m \leq n$ words of length $n$ then, for every $k \geq n + m$ , it contains at most...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study the complexity of the infinite word $u_{β}$ associated with the Rényi expansion of $1$ in an irrational base $β > 1$ . When $β$ is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity $ℂ (n) = n + 1$ . For $β$ such that $d_{β} (1) = t_{1} t_{2} \dots t_{m}$ is finite we provide a simple description of the structure of special factors of the word $u_{β}$ . When $t_{m} = 1$ we show that $ℂ (n) = (m - 1) n + 1$ . In the cases when $t_{1} = t_{2} = \dots = t_{m - 1}$ or $t_{1} > max {t_{2}, \dots, t_{m - 1}}$ we show that the first difference of the complexity function $ℂ (n + 1) - ℂ (n)$ takes value in ${m - 1, m}$ for every $n$ , and consequently...

Substitution invariant sturmian bisequences

Bruno Parvaix (1999)

Journal de théorie des nombres de Bordeaux

Similarity:

We prove that a Sturmian bisequence, with slope $α$ and intercept $ρ$ , is fixed by some non-trivial substitution if and only if $α$ is a Sturm number and $ρ$ belongs to $ℚ (α)$ . We also detail a complementary system of integers connected with Beatty bisequences.