Search

Given a finite alphabet A and a quasi-metric d over A ⁎ , we introduce the relation τ d , k ⊆ A ⁎ × A ⁎ such that (x , y) ∈ τ d , k holds whenever d (x , y) ≤ k. The error detection capability of variable-length codes is expressed in term of conditions over τ d , k. With respect to the prefix metric, the factor one, and any quasi-metric associated with some free monoid (anti-)automorphism, we prove that one can decide whether a given regular variable-length code satisfies any of those error detection constraints. [ABSTRACT FROM AUTHOR]

• Given an alphabet A , and an (anti-)automorphism θ , a set L ⊆ A ⁎ is θ -invariant if θ (L) = L. • In the framework of θ -invariant sets, a defect effect is highlighted. • Several non-trivial examples of finite complete θ -invariant codes are presented. • Over a finite alphabet, any regular non complete θ -invariant code can be embedded into a complete one. • Given a thin θ -invariant code, being a maximal code, or being maximal in the family of θ -invariant codes, or being complete are equivalent properties. Let A be an arbitrary alphabet and let θ be an (anti-)automorphism of A ⁎ (by definition, such a correspondence is determinated by a permutation of the alphabet). This paper deals with sets which are invariant under θ (θ -invariant for short) that is, languages L satisfying θ (L) ⊆ L. We establish an extension of the famous defect theorem. With regard to the so-called notion of completeness, we provide a series of examples of finite complete θ -invariant codes. Moreover, we establish a formula which allows to embed any non-complete θ -invariant code into a complete one. As a consequence, in the family of the so-called thin θ -invariant codes, maximality and completeness are two equivalent notions. [ABSTRACT FROM AUTHOR]

Given a binary word relation τ onto A ⁎ and a finite language X ⊆ A ⁎ , a τ -Gray cycle over X consists in a permutation (w [ i ]) 0 ≤ i ≤ | X | − 1 of X such that each word w [ i ] is an image under τ of the previous word w [ i − 1 ]. We define the complexity measure λ A , τ (n) , equal to the largest cardinality of a language X having words of length at most n , and st. some τ -Gray cycle over X exists. The present paper is concerned with τ = σ k , the so-called k -character substitution, st. (u , v) ∈ σ k holds if, and only if, the Hamming distance of u and v is k. We present loopless (resp., constant amortized time) algorithms for computing specific maximum length σ k -Gray cycles. [ABSTRACT FROM AUTHOR]

We investigate inference of variable-length codes in other domains of computer science, such as noisy information transmission or information retrieval-storage: in such topics, traditionally mostly constant-length codewords act. The study is relied upon the two concepts of independent and closed sets: given an alphabet A and a binary relation τ ⊆ A ⁎ × A ⁎ , a set X ⊆ A ⁎ is τ - independent if τ (X) ∩ X = ∅ ; X is τ - closed if τ (X) ⊆ X. We focus to those word relations whose images are computed by applying some peculiar combinations of deletion, insertion, or substitution. In particular, characterizations of variable-length codes that are maximal in the families of τ -independent or τ -closed codes are provided. [ABSTRACT FROM AUTHOR]

Abstract: Let be an arbitrary submonoid of the free monoid , and let be a variable length code (for short a code). is weakly -complete iff any word in is a factor of some word in [J. Néraud, C. Selmi, Free monoid theory: Maximality and completeness in arbitrary submonoids, Internat. J. Algebra Comput. 13 (5) (2003) 507–516]. Given a regular submonoid , and given an arbitrary code , we are interested in the existence of a weakly -complete code that contains . Actually, in [J. Néraud, Completing a code in a regular submonoid, in: Acts of MCU’2004, Lect. Notes Comput. Sci. 3354 (2005) 281–291; J. Néraud, Completing a code in a submonoid of finite rank, Fund. Inform. 74 (2006) 549–562], by presenting a general formula, we have established that, in any case, such a code exists. In the present paper, we prove that any regular circular code may be embedded into a weakly -complete one iff the minimal automaton with behavior has a synchronizing word. As a consequence of our result an extension of the famous theorem of Schützenberger is stated for regular circular codes in the framework of regular submonoids. We study also the behaviour of the subclass of uniformly synchronous codes in connection with these questions. [Copyright &y& Elsevier]

Abstract: Let M be a submonoid of the free monoid , and let be a variable length code (for short a code). X is weakly M-complete if any word in M is a factor of some word in [J. Néraud, C. Selmi, Free monoid theory: maximality and completeness in arbitrary submonoids, Internat. J. Algorithms Comput. 13(5) (2003) 507–516]. Given a code , we are interested in the construction of a weakly M-complete code that contains X, if it exists. In the case where M and X are regular sets, the existence of such a code has been established [J. Néraud, Completing a code in a regular submonoid of the free monoid, in acts of MCU’2004, Lecture Notes in Computer Sciences, Vol. 3354, Springer, Berlin, 2005, pp. 281–291; J. Néraud, On the completion of codes in submonoids with finite rank, Fund. Inform., to appear]. Actually, this result lays upon a method of construction that preserves the regularity of sets. As well known, any regular (or finite) code may be embedded into a regular (finite) prefix code that is complete in . In the framework of the weak completeness, we prove that the following problem is decidable: Instance: A regular submonoid M of , and a regular (or finite) prefix code . Question: Does a weakly M-complete regular (finite) prefix code containing X exist? [Copyright &y& Elsevier]

In this paper, we discuss the different notions of local topological density for subsets of the free monoid A*. We introduce the notion of weak completeness for a set X, relatively to an arbitrary submonoid M of A*. For the so-called strongly M-thin codes, we establish that weak completeness is equivalent to maximality in M. This constitutes a new generalization of a famous result due to Schützenberger. [ABSTRACT FROM AUTHOR]

Girod's encoding method has been introduced in order to efficiently decode from both directions messages encoded by using finite prefix codes. In the present paper, we generalize this method to finite codes with a finite deciphering delay. In particular, we show that our decoding algorithm can be realized by a deterministic finite transducer. We also investigate some properties of the underlying unlabeled graph. [ABSTRACT FROM AUTHOR]