On the Completion of Codes in Submonoids with Finite Rank

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 �.