Search

• 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]

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]