Displaying similar documents to “Binary patterns in binary cube-free words: Avoidability and growth”

On the growth rates of complexity of threshold languages

Arseny M. Shur, Irina A. Gorbunova (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Threshold languages, which are the (/(–1))-free languages over -letter alphabets with ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over letters tends to a constant α ^ ≈ 1 . 242 as tends to infinity.

Comparing Complexity Functions of a Language and Its Extendable Part

Arseny M. Shur (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.

From indexed grammars to generating functions

Jared Adams, Eric Freden, Marni Mishna (2013)

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

Similarity:

We extend the DSV method of computing the growth series of an unambiguous context-free language to the larger class of indexed languages. We illustrate the technique with numerous examples.

Binary words avoiding the pattern AABBCABBA

Pascal Ochem (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that there are three types of infinite words over the two-letter alphabet {0,1} that avoid the pattern . These types, , , and , differ by the factor complexity and the asymptotic frequency of the letter 0. Type has polynomial factor complexity and letter frequency 1 2 . Type has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type is obtained from type ...

On differentiation functions, structure functions, and related languages of context-free grammars

Jürgen Dassow, Victor Mitrana, Gheorghe Păun, Ralf Stiebe (2004)

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

Similarity:

We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or k -narrow) iff its differentiation function is bounded by a constant (by k ). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability of the...