Skip to Main content Skip to Navigation
Journal articles

Completing codes in a sofic shift

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

Cited literature [17 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619734
Contributor : Marie-Pierre Béal <>
Submitted on : Thursday, October 6, 2011 - 2:13:40 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Saturday, January 7, 2012 - 2:20:37 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619734, version 1

Citation

Marie-Pierre Béal, Dominique Perrin. Completing codes in a sofic shift. Theoretical Computer Science, Elsevier, 2009, 410 (43), pp.4423-4431. ⟨hal-00619734⟩

Share

Metrics

Record views

270

Files downloads

275