2018/01/31 by Jean Néraud, Carla Selmi
Computer Science · Mathematics · #cs.CL #cs.DM #math.CO
paper · pdf · doi:10.1016/j.tcs.2018.08.022
published as Theoretical Computer Science, Elsevier · arXiv admin note: text overlap with arXiv:1705.05564
arxiv created 2018/09/03 · arxiv updated 2018/09/06
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.