Displaying similar documents to “On conjugacy of languages”

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.

On the simplest centralizer of a language

Paolo Massazza, Petri Salmela (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

Given a finite alphabet and a language , the centralizer of is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of (with respect to a lexicographic order) is prefix distinguishable in then the centralizer of is as simple as possible, that is, the submonoid . This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.

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

Atoms and partial orders of infinite languages

Werner Kuich, N. W. Sauer (2001)

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

Similarity:

We determine minimal elements, i.e., atoms, in certain partial orders of factor closed languages under ⊆ . This is in analogy to structural Ramsey theory which determines minimal structures in partial orders under embedding.

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

Linear size test sets for certain commutative languages

Štěpán Holub, Juha Kortelainen (2001)

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

Similarity:

We prove that for each positive integer n , the finite commutative language E n = c ( a 1 a 2 ⋯ a n ) possesses a test set of size at most 5 n . Moreover, it is shown that each test set for E n has at least n - 1 elements. The result is then generalized to commutative languages L containing a word w such that (i) alph ( w ) = alph ( L ) ; and (ii) each symbol a ∈ alph ( L ) occurs at least twice in w if it occurs at least twice in some word of L : each such L possesses a test set of size 11 n , where n = Card ( alph ( L ) ) . The considerations rest on the analysis of some basic types...