Codes and sofic constraints

Marie-Pierre Béal (1) , Dominique Perrin (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

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.

Domaines: Algorithme et structure de données [cs.DS]

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