Skip to Main content Skip to Navigation
Journal articles

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

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 (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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-normandie-univ.archives-ouvertes.fr/hal-02117030
Contributor : Carla Selmi <>
Submitted on : Wednesday, May 1, 2019 - 11:05:25 PM
Last modification on : Friday, May 17, 2019 - 1:41:38 AM

File

Invariance-Neraud-Selmi.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02117030, version 1

Citation

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⟩

Share

Metrics

Record views

35

Files downloads

74