Substitution invariant sturmian bisequences

Bruno Parvaix

Displaying similar documents to “Substitution invariant sturmian bisequences”

*-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...

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...

Combinatorial properties of infinite words associated with cut-and-project sequences

Louis-Sébastien Guimond, Zuzana Masáková, Edita Pelantová (2003)

Journal de théorie des nombres de Bordeaux

Similarity:

The aim of this article is to study certain combinatorial properties of infinite binary and ternary words associated to cut-and-project sequences. We consider here the cut-and-project scheme in two dimensions with general orientation of the projecting subspaces. We prove that a cut-and-project sequence arising in such a setting has always either two or three types of distances between adjacent points. A cut-and-project sequence thus determines in a natural way a symbolic sequence (infinite...

Episturmian words: a survey

Amy Glen, Jacques Justin (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper, we survey the rich theory of infinite which generalize to any finite alphabet, in a rather resembling way, the well-known family of on two letters. After recalling definitions and basic properties, we consider that allow for a deeper study of these words. Some properties of factors are described, including factor complexity, palindromes, fractional powers, frequencies, and return words. We also consider lexicographical properties of episturmian words, as well as their...

On low-complexity bi-infinite words and their factors

Alex Heinis (2001)

Journal de théorie des nombres de Bordeaux

Similarity:

In this paper we study bi-infinite words on two letters. We say that such a word has stiffness $k$ if the number of different subwords of length $n$ equals $n + k$ for all $n$ sufficiently large. The word is called $k$ -balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most $k$ . In the present paper we give a complete description of the class of bi-infinite words of stiffness $k$ and show that the number of subwords of length $n$ from this class has...

A note on univoque self-sturmian numbers

Jean-Paul Allouche (2008)

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

Similarity:

We compare two sets of (infinite) binary sequences whose suffixes satisfy extremal conditions: one occurs when studying iterations of unimodal continuous maps from the unit interval into itself, but it also characterizes univoque real numbers; the other is a disguised version of the set of characteristic sturmian sequences. As a corollary to our study we obtain that a real number $β$ in $(1, 2)$ is univoque and self-sturmian if and only if the $β$ -expansion of $1$ is of the form $1 v$ , where $v$ is a characteristic...

Morphisms fixing words associated with exchange of three intervals

Petr Ambrož, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider words coding exchange of three intervals with permutation (3,2,1), here called 3iet words. Recently, a characterization of substitution invariant 3iet words was provided. We study the opposite question: what are the morphisms fixing a 3iet word? We reveal a narrow connection of such morphisms and morphisms fixing Sturmian words using the new notion of amicability.