Affiliations: lifar/Département Informatique,
Université de ROUEN, France. E-mail: [email protected]
Abstract: Let M be a submonoid of the free monoid A*, and let X⊂M be a
variable length code (for short a code). X is weakly M-complete if and only if
any word in M is a factor of some word in X* (cf [20]). In this paper, which is
the full version of a result presented in [17], we are interested by an
effective computation of a weakly M-complete code containing X, namely
�⊂M. In this framework, we consider the class of submonoids M of A*
which have finite rank. We define the rank of M as the rank of the minimal
automaton with behavior M, i.e. the smallest positive integer r such that a
word w satisfies ∣Q·w∣=r, where Q stands for the set of states
(the action of the word w may be not defined on some state in Q). Regular
submonoids are the most typical example of submonoids with finite rank. Given a
submonoid with finite rank M⊂A*, and given a code X⊂M, we present a
method of completion which makes only use of regular or boolean operations on
sets. As a consequence, if M and X are regular sets then so is �.
Keywords: Words, free monoid, submonoid, variable length code, minimal automaton, rank, den-sity, completeness, local density, weakly complete, strongly thin, completable, completion of a code
