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

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

1 LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
2 CA - LITIS - Equipe Combinatoire et algorithmes

Let 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 so-called 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 (two-way) 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.

Keywords: synchronizing delay; variable length code; verbal synchronizing delay; word; antimorphism; bifix; circular; code; complete; deciphering delay; defect; delay; embedding; equation; literal; maximal; morphism; prefix

Domains: Computer Science [cs]; Formal Languages and Automata Theory [cs.FL]

Jean Néraud, Carla Selmi. Invariance: a Theoretical Approach for Coding Sets of Words Modulo Literal (Anti)Morphisms. Springer, LNCS., 2017, pp.214-227. ⟨hal-02117030⟩