Complete codes in a sofic shift - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2002

Complete codes in a sofic shift

Marie-Pierre Béal
  • Fonction : Auteur
  • PersonId : 841350
Dominique Perrin

Résumé

We define a code in a sofic shift as a set of blocks of symbols of the shift such that any block of the shift has at most one decomposition in code words. It is maximal if it is not strictly included in another one. Such a code is complete in the sofic shift if any block of the shift occurs within some concatenation of code words. We prove that a maximal code in an irreducible sofic shift is complete in this shift. We give an explicit construction of a regular completion of a regular code in a sofic shift. This extends the well known result of Ehrenfeucht and Rozenberg to the case of codes in sofic systems. We also give a combinatorial proof of a result concerning the polynomial of a code in a sofic shift.
Fichier principal
Vignette du fichier
hal.pdf (138.9 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00619856 , version 1 (06-10-2011)

Identifiants

  • HAL Id : hal-00619856 , version 1

Citer

Marie-Pierre Béal, Dominique Perrin. Complete codes in a sofic shift. 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), 2002, France. pp.547-558. ⟨hal-00619856⟩
68 Consultations
208 Téléchargements

Partager

Gmail Facebook X LinkedIn More