A Characterization of Complete Finite Prefix Codes in a submonoid of A*

Jean Néraud
LIFAR, Université de Rouen, Place Émile Blondel, 76821 Mont-Saint-Aignan, France

Carla Selmi
LIFAR, Université de Rouen, Place Émile Blondel, 76821 Mont-Saint-Aignan, France

Abstract: Given an arbitrary submonoid M of the free monoid A*, and given a subset X of M, X is M-complete if any word of M is a factor of some word in X*. The submonoid X* itself is weakly M-dense. We apply a result from Latteux and Timmerman and a result from Litovsky for obtaining a new characterization of the existence of a finite weakly M-complete prefix code: such a set exists iff M is weakly dense in its right unitary hull (i.e. the smallest right unitary submonoid of A* that contains AM). This leads to an efficient algorithm for deciding whether a given finite prefix subset of a finitely generated submonoid M is (weakly) M-complete.

Keywords: Free monoid; submonoid; unitary, variable lengths codes; codes; prefix; suffix; bifix; complete; dense; maximal; local density; local completeness; maximal codes; codes maximal in a submonoid.

Page d'accueil de l'atelier
Présentation de l'atelier
Description des activités
Bibliographie