Invariance: a Theoretical Approach for Coding Sets of Words Modulo Literal (Anti)Morphisms - Normandie Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

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

Résumé

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 in the framework of some special families of $\theta$-invariant codes such as prefix (bifix) codes, codes with a finite deciphering delay, uniformly synchronized 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.
Soit $A$ un alphabet fini ou dénombrable}et soit $\theta$ un (anti)morphisme litt\éra} dans $A^*$ (par définition, une telle application est déterminée par une permutation sur l'alphabet). Le présent article est consacré à l' étude des ensembles qui sont invariants par $\theta$ ($\theta$-invariants pour abréger). Nous établissons une extension du célèbre théorème du défaut. En outre, nous prouvons que pour les codes $\theta$-invariants qui sont coupants, la maximalité et la complétude sont deux notions équivalentes. Nous prouvons également qu'une propriété semblable peur être formulée dans le cadre de quelques familles particulières de codes: les codes préfixes, bifixes, les codes à d\'elai de déchiffrage fini, les codes uniformément synchronisés et les codes circulaires. En ce qui concerne une classe particulière d'antimorphismes involutifs, nous prouvons que tout code $\theta$-invariant peut être plongé dans un code $\theta$-invariant complet.
Fichier principal
Vignette du fichier
main.pdf (174.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01519557 , version 1 (15-05-2017)
hal-01519557 , version 2 (01-07-2017)
hal-01519557 , version 3 (20-07-2017)
hal-01519557 , version 4 (27-07-2017)

Licence

Copyright (Tous droits réservés)

Identifiants

Citer

Jean Néraud, Carla Selmi. Invariance: a Theoretical Approach for Coding Sets of Words Modulo Literal (Anti)Morphisms. WORDS 2017, Srečko Brlek ; Christophe Reutenauer, Sep 2017, Montréal, QC, France. ⟨hal-01519557v4⟩
247 Consultations
109 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More