A Characterization of Complete Finite Prefix Codes in an Arbitrary Submonoid of A*

Given an arbitrary submonoid M of the free monoid A*, and given a subset X of M, X is weakly 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 two results from [8, 9] for obtaining a new characterization of the existence of a finite weakly M-complete prefix set: such a set exists iff M itself is weakly dense in its right unitary hull. This leads to an efficient algorithmic for deciding whether a given finite prefix subset of a finitely generated submonoid M is (weakly) M-complete.