Displaying similar documents to “Finite Completion of comma-free codes Part 2”

Finite Completion of comma-free codes Part 1

Nguyen Huong Lam (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper is the first step in the solution of the problem of finite completion of comma-free codes. We show that every finite comma-free code is included in a finite comma-free code of particular kind, which we called, for lack of a better term, canonical comma-free code. Certainly, finite maximal comma-free codes are always canonical. The final step of the solution which consists in proving further that every canonical comma-free code is completed to a finite maximal comma-free...

Finite completion of comma-free codes. Part 1

Nguyen Huong Lam (2004)

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

Similarity:

This paper is the first step in the solution of the problem of finite completion of comma-free codes. We show that every finite comma-free code is included in a finite comma-free code of particular kind, which we called, for lack of a better term, canonical comma-free code. Certainly, finite maximal comma-free codes are always canonical. The final step of the solution which consists in proving further that every canonical comma-free code is completed to a finite maximal comma-free code,...

A hierarchy for circular codes

Giuseppe Pirillo (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We first prove an extremal property of the infinite Fibonacci word : the family of the palindromic prefixes {} of is not only a circular code but “almost” a comma-free one (see Prop. 12 in Sect. 4). We also extend to a more general situation the notion of a necklace introduced for the study of trinucleotides codes on the genetic alphabet, and we present a hierarchy relating two important classes of codes, the comma-free codes and the circular ones.

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.

Compatibility relations on codes and free monoids

Tomi Kärki (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

A compatibility relation on letters induces a reflexive and symmetric relation on words of equal length. We consider these word relations with respect to the theory of variable length codes and free monoids. We define an -code and an -free monoid for arbitrary word relations and . Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are -codes. Coding capabilities of relational codes are measured algorithmically by finding minimal and maximal relations....