Invariance: a theoretical approach for coding sets of words modulo literal (anti)morphisms

EasyChair Preprint 2198

Abstract

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 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: Circular code, Finite deciphering delay, Synchronizing delay, antimorphism, bifix, circular, code, complete, complete regular invariant code, countable alphabet, deciphering delay, defect, equation, 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, thin code, thin invariant code, uniformly synchronized code, variable-length code, word, word modulo

@booklet{EasyChair:2198,
  author    = {Jean Néraud and Carla Selmi},
  title     = {Invariance: a theoretical approach for coding sets of words modulo literal (anti)morphisms},
  howpublished = {EasyChair Preprint 2198},
  year      = {EasyChair, 2019}}