Hereditary properties of words

József Balogh; Béla Bollobás

Displaying similar documents to “Hereditary properties of words”

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

Containers and wide diameters of $P_{3} (G)$

Daniela Ferrero, Manju K. Menon, A. Vijayakumar (2012)

Mathematica Bohemica

Similarity:

The $P_{3}$ intersection graph of a graph $G$ has for vertices all the induced paths of order 3 in $G$ . Two vertices in $P_{3} (G)$ are adjacent if the corresponding paths in $G$ are not disjoint. A $w$ -container between two different vertices $u$ and $v$ in a graph $G$ is a set of $w$ internally vertex disjoint paths between $u$ and $v$ . The length of a container is the length of the longest path in it. The $w$ -wide diameter of $G$ is the minimum number $l$ such that there is a $w$ -container of length at most $l$ between any pair...

On Christoffel classes

Jean-Pierre Borel, Christophe Reutenauer (2006)

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

Similarity:

We characterize conjugation classes of Christoffel words (equivalently of standard words) by the number of factors. We give several geometric proofs of classical results on these words and sturmian words.

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

Cycle and path embedding on 5-ary N-cubes

Tsong-Jie Lin, Sun-Yuan Hsieh, Hui-Ling Huang (2009)

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

Similarity:

We study two topological properties of the 5-ary $n$ -cube $Q_{n}^{5}$ . Given two arbitrary distinct nodes $x$ and $y$ in $Q_{n}^{5}$ , we prove that there exists an $x$ - $y$ path of every length ranging from $2 n$ to $5^{n} - 1$ , where $n \geq 2$ . Based on this result, we prove that $Q_{n}^{5}$ is 5-edge-pancyclic by showing that every edge in $Q_{n}^{5}$ lies on a cycle of every length ranging from $5$ to $5^{n}$ .

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