Invariance: a Theoretical Approach for Coding Sets of Words Modulo Literal (Anti)Morphisms

Jean Néraud (1, 2) , Carla Selmi (2, 1)

1 UNIROUEN - Université de Rouen Normandie
2 LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes

Let $A$ be a finite or countable alphabet and let $\theta$ 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 $\theta$ ($\theta$-invariant for short). We establish an extension of the famous defect theorem. Moreover, we prove that for the so-called thin $\theta$-invariant codes, maximality and completeness are two equivalent notions. We prove that a similar property holds for some special families of $\theta$-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 $\theta$-invariant code may be embedded into a complete one.

Mots clés: word; code; variable length code; morphism; antimorphism; literal; prefix; bifix; deciphering delay; synchronizing delay; circular; defect; equation; maximal; complete.

Domaines: Mathématique discrète [cs.DM]; Théorie de l'information [cs.IT]; Combinatoire [math.CO]; Théorie de l'information et codage [math.IT]

Jean Néraud, Carla Selmi. Invariance: a Theoretical Approach for Coding Sets of Words Modulo Literal (Anti)Morphisms. 2017. ⟨hal-01519557v1⟩