Displaying similar documents to “On equivalence of two tests for codes.”

Decidability of code properties

Henning Fernau, Klaus Reinhardt, Ludwig Staiger (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

We explore the borderline between decidability and undecidability of the following question: “Let be a class of codes. Given a machine 𝔐 of type , is it decidable whether the language L ( 𝔐 ) lies in or not?” for codes in general, -codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.

A property of biprefix codes

Martine Leonard (1988)

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

Similarity:

On a class of infinitary codes

Nguyen Huong Lâm, Do Long Van (1990)

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

Similarity:

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 coding morphisms for zigzag codes

Do Long Van, Bertrand Le Saëc, Igor Litovsky (1992)

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

Similarity:

On a complete set of operations for factorizing codes

Clelia De Felice (2006)

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

Similarity:

It is known that the class of factorizing codes, i.e., codes satisfying the factorization conjecture formulated by Schützenberger, is closed under two operations: the classical composition of codes and substitution of codes. A natural question which arises is whether a finite set 𝒪 of operations exists such that each factorizing code can be obtained by using the operations in 𝒪 and starting with prefix or suffix codes. 𝒪 is named here a complete set of operations (for factorizing codes)....