Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: weakly complete

Sortuj według:

Ogranicz wyniki do:

On the Completion of Codes in Submonoids with Finite Rank

Néraud J.

Fundamenta Informaticae

2006

Vol. 74, nr 4

549-562

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