Displaying similar documents to “On the simplest centralizer of a language”

Uniformly bounded duplication codes

Peter Leupold, Victor Mitrana (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

Duplication is the replacement of a factor within a word by . This operation can be used iteratively to generate languages starting from words or sets of words. By undoing duplications, one can eventually reach a square-free word, the original word's duplication root. The duplication root is unique, if the length of duplications is fixed. Based on these unique roots we define the concept of duplication code. Elementary properties are stated, then the conditions under which infinite...

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.

On conjugacy of languages

Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2001)

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

Similarity:

We say that two languages X and Y are conjugates if they satisfy the conjugacy equation X Z = Z Y for some language Z . We study several problems associated with this equation. For example, we characterize all sets which are conjugated v i a a two-element biprefix set Z , as well as all two-element sets which are conjugates.

On some problems related to palindrome closure

Michelangelo Bucci, Aldo de Luca, Alessandro De Luca, Luca Q. Zamboni (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper, we solve some open problems related to (pseudo)palindrome closure operators and to the infinite words generated by their iteration, that is, standard episturmian and pseudostandard words. We show that if is an involutory antimorphism of , then the right and left -palindromic closures of any factor of a -standard word are also factors of some -standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure...

Finite completion of comma-free codes. Part 2

Nguyen Huong Lam (2004)

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

Similarity:

This paper is a sequel to an earlier paper of the present author, in which it was proved that every finite comma-free code is embedded into a so-called (finite) canonical comma-free code. In this paper, it is proved that every (finite) canonical comma-free code is embedded into a finite maximal comma-free code, which thus achieves the conclusion that every finite comma-free code has finite completions.