Download PDFOpen PDF in browserInvariance: a theoretical approach for coding sets of words modulo literal (anti)morphismsEasyChair Preprint no. 219812 pages•Date: December 18, 2019AbstractLet A be a finite or countable alphabet and let θ be literal (anti)morphism 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). We establish an extension of the famous defect theorem. Moreover, we prove that for the socalled thin θinvariant codes, maximality and completeness are two equivalent notions. We prove that a similar property holds for some special families of θinvariant codes such as prefix (bifix) codes, codes with a finite deciphering delay, uniformly synchronous codes and circular codes. For a special class of involutive antimorphisms, we prove that any regular θinvariant code may be embedded into a complete one. Keyphrases: antimorphism, bifix, circular, Circular code, code, complete, complete regular invariant code, countable alphabet, deciphering delay, defect, equation, Finite deciphering delay, free monoid, invariant code, invariant set, literal, maximal, maximal code, morphism, non complete, non complete invariant code, non trivial equation, overlapping free word, prefix, prefix code, regular code, regular invariant code, smallest invariant free submonoid, Synchronizing delay, thin code, thin invariant code, uniformly synchronized code, variablelength code, word, word modulo
