On the Completion of Codes in Submonoids with Finite Rank
Titel:
On the Completion of Codes in Submonoids with Finite Rank
Auteur:
Néraud, Jean
Verschenen in:
Fundamenta informaticae
Paginering:
Jaargang 74 (2006) nr. 4 pagina's 549-562
Jaar:
2006-12-12
Inhoud:
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 \^{X} ⊂ 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 \^{X}.
Tijdschrift beschrijving