Skip to Main content Skip to Navigation
Journal articles

Codes and sofic constraints

Abstract : We study the notion of a code in a sofic subshift. We first give a generalization of the Kraft-McMillan inequality to this case. We then prove that the polynomial of the alphabet in an irreducible sofic shift divides the polynomial of any finite code which is complete for this sofic shift. This settles a conjecture from Reutenauer.
Document type :
Journal articles
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619227
Contributor : Marie-Pierre Béal <>
Submitted on : Monday, September 5, 2011 - 6:14:35 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Tuesday, December 6, 2011 - 2:28:51 AM

Files

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619227, version 1

Collections

Citation

Marie-Pierre Béal, Dominique Perrin. Codes and sofic constraints. Theoretical Computer Science, Elsevier, 2005, 340 (2), pp.381-393. ⟨hal-00619227⟩

Share

Metrics

Record views

251

Files downloads

297