Embedding a $θ$-invariant code into a complete one
This work addresses a theoretical problem in formal language theory for researchers studying codes and automorphisms, but it appears incremental as it extends existing defect theorem results.
The paper tackles the problem of embedding non-complete θ-invariant codes into complete ones, establishing a formula for this embedding and showing that in thin θ-invariant codes, maximality and completeness are equivalent.
Let A be a finite or countable alphabet and let $θ$ be a literal (anti-)automorphism onto 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 such that $θ$ (L) is a subset of L.We establish an extension of the famous defect theorem. With regards 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.