A length bound for binary equality words

Jana Hadravová

Displaying similar documents to “A length bound for binary equality words”

Borders and roots of a word

Silberger, D.M. (1971)

Portugaliae mathematica

Similarity:

Periodicity problem of substitutions over ternary alphabets

Bo Tan, Zhi-Ying Wen (2008)

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

Similarity:

In this paper, we characterize the substitutions over a three-letter alphabet which generate a ultimately periodic sequence.

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

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

Equations on partial words

Francine Blanchet-Sadri, D. Dakota Blair, Rebeca V. Lewis (2009)

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

Similarity:

It is well-known that some of the most basic properties of words, like the commutativity ( $x y = y x$ ) and the conjugacy ( $x z = z y$ ), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation $x^{m} y^{n} = z^{p}$ has only periodic solutions in a free monoid, that is, if $x^{m} y^{n} = z^{p}$ holds with integers $m, n, p \geq 2$ , then there exists a word $w$ such that $x, y, z$ are powers of $w$ . This result, which received a lot of attention, was first proved...

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

A test-set for $k$ -power-free binary morphisms

F. Wlazinski (2001)

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

Similarity:

A morphism $f$ is $k$ -power-free if and only if $f (w)$ is $k$ -power-free whenever $w$ is a $k$ -power-free word. A morphism $f$ is $k$ -power-free up to $m$ if and only if $f (w)$ is $k$ -power-free whenever $w$ is a $k$ -power-free word of length at most $m$ . Given an integer $k \geq 2$ , we prove that a binary morphism is $k$ -power-free if and only if it is $k$ -power-free up to $k^{2}$ . This bound becomes linear for primitive morphisms: a binary primitive morphism is $k$ -power-free if and only if it is $k$ -power-free up to $2 k + 1$ ...

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.