Complexity of infinite words associated with beta-expansions

Christiane Frougny; Zuzana Masáková; Edita Pelantová

Displaying similar documents to “Complexity of infinite words associated with beta-expansions”

Palindromic complexity of infinite words associated with non-simple Parry numbers

L&#039;ubomíra Balková, Zuzana Masáková (2009)

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

Similarity:

We study the palindromic complexity of infinite words $u_{β}$ , the fixed points of the substitution over a binary alphabet, $ϕ (0) = 0^{a} 1$ , $ϕ (1) = 0^{b} 1$ , with $a - 1 \geq b \geq 1$ , which are canonically associated with quadratic non-simple Parry numbers $β$ .

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

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

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.

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

On some properties of doubly-periodic words

Claudio Baiocchi (1997)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni

Similarity:

We study the functional equation: $(1) A B C = C D A$ where $A, B, C$ and $D$ are words over an alphabet $A$ . In particular we prove a «structure result» for the inner factors $B, D$ : for suitably chosen words $X, Y, Z$ one has: $(2) B = X Y Z$ , $D = Z Y X$ $(2) B = X Y Z$ , $D = Z Y X$ $(2) B = X Y Z$ , $D = Z Y X$ $(2) B = X Y Z$ , $D = Z Y X$ . It is a generalization of the Lyndon-Schützenberger's Theorem (see [7]): if in (1) $A$ or $C$ is empty, formula (2) holds true with one among $X, Y, Z$ which can be chosen empty.

On the distribution of characteristic parameters of words

Arturo Carpi, Aldo de Luca (2002)

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

Similarity:

For any finite word $w$ on a finite alphabet, we consider the basic parameters $R_{w}$ and $K_{w}$ of $w$ defined as follows: $R_{w}$ is the minimal natural number for which $w$ has no right special factor of length $R_{w}$ and $K_{w}$ is the minimal natural number for which $w$ has no repeated suffix of length $K_{w}$ . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

Forbidden factors and fragment assembly

F. Mignosi, A. Restivo, M. Sciortino (2001)

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

Similarity:

In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word $w$ from a given set $I$ of substrings (fragments) of a word $w$ . We introduce an hypothesis involving the set of fragments $I$ and the maximal length $m (w)$ of the minimal forbidden factors of $w$ . Such hypothesis allows us to reconstruct uniquely the word $w$ from the set...