Completing prefix codes in submonoids. (Q2490823)

The paper deals with some aspect of the weak completeness of prefix codes, defined in the work of Jean Névand and Carla Selmi [Int. J. Algebra Comput. 13, No.~5, 507--516 (2003; Zbl 1064.68076)]. For a given submonoid \(M\) of a free monoid \(A^*\), a code \(X\) is said to be weakly \(M\)-complete if and only if \(X\subseteq M\) and each word in \(M\) is a factor of some word in \(X^*\). It has been proved that for a regular submonoid \(M\)of \(A^*\) and a regular prefix code \(X\subseteq M\) the problem \textit{`Does a weakly \(M\)-complete regular prefix code containing \(X\) exist?'} is decidable. If such code exists then it is constructed by the algorithm that computes the solution of this problem.