Embedding a θ-invariant code into a complete one

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.

Authors

• Jean Néraud
• Carla Selmi

Keywords

• Antimorphism
• Anti-automorphism
• Automorphism
• (Anti-)automorphism
• Bernoulli distribution
• Bifix
• Code
• Complete
• Context-free
• Defect
• Equation
• Finite
• Invariant
• Involutive
• Label
• Maximal
• Morphism
• Order
• Overlap
• Overlapping-free
• Prefix
• Regular
• Suffix
• Thin
• Tree
• θ-Invariant
• θ-Code
• Uniform
• Variable-length code
• Word