Download PDFOpen PDF in browser

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

EasyChair Preprint 2198

12 pagesDate: December 18, 2019

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}
Download PDFOpen PDF in browser