On the Completion of Codes in Submonoids with Finite Rank

• Autorzy: Néraud J.
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

word; free monoid; submonoid; variable lenght code; minimal automaton; rank; density; completeness; local density; weakly complete; strongly thin; completable; completion of a code

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 549--562
• Opis fizyczny: bibliogr. 26 poz.

Twórcy

autor

Néraud J.

• Université de Rouen, Faculté des Sciences, Campus du Marrillet, lifar / Départment Informatique, Avenue de l'Universitaté, BP 12, 76801 Saint Etienne du Rouvray cedex, France,

Bibliografia

• [1] Ananichev D.S., Cherubini A. and M.V. Volkov, Image reducing words and subgroups of free groups, Theoret. Comput. Sci. 307 (2003) 77-92.
• [2] Béal M.-P., "Codage Symbolique",Masson, 1993.
• [3] Blanchard F and G. Hansel, systèmes codés, Theoret. Comput. Sci. 44 (1986) 17-49.
• [4] Berstel J., and D. Perrin, "Theory of Codes", Academic Press, 1985.
• [5] On maximal codes with bounded synchronizing delay, Theoret. Comput. Sci. 204 (1998) 11-28.
• [6] Bruyère V. and M. Latteux, Variable-Length Maximal Codes, in acts of ICALP'96, Lecture Notes Comput. Sci. 1099 (1996) 24-47.
• [7] Bruyère V., Wang V. and L. Zhang, On completion of codes with deciphering delay, European J. Combin. 11 (1990) 513-521.
• [8] Carpi A., On synchronizing unambigous automata, Theoret. Comput. Sci. 60 (1988) 285-296.
• [9] Devolder J. and I. Litovsky, Finitely generated bi !-languages, Theoret. Comput. Sci. 85 (1991) 33-52.
• [10] De Felice C. and A. Restivo, Some results on finite maximal codes, Theoret. Info. and Appl. 19, 4 (1985) 383-403.
• [11] Ehrenfeucht A and S. Rozenberg, Each regular code is included in a regular maximal one, Theoret. Info. And Appl. 20, 1 (1985) 89-96.
• [12] Guesnet Y., On maximal codes with finite interpreting delay, Theoret. Comput. Sci. 273 (2002) 167-183.
• [13] Latteux M. and E. Timmerman, Finitely generated !-languages, Info. Process. Letter 23 (1986) 171-175.
• [14] Litovsky I., Prefix-free languages as !-generators, Info. Process. Letters 37 (1991) 61-65.
• [15] Litovsky I. and E. Timmerman, On generator of rationnal !-languages, Theoret. Comput. Sci. 53 (1987) 187-200.
• [16] Nguyen Huong Lam, Finite maximal solid codes, Theoret. Comput. Sci. 262 (2001) 333-347.
• [17] Néraud J., Completing a code in a regular submonoid, in acts of MCU'2004, St Petersburg, Russia, M. Margenstern ed., Lect. Notes Comput. Sci. 3354 (2005) 281-291.
• [18] Néraud J and C. Selmi, On codes with a finite deciphering delay: constructing uncompletable words, Theoret. Comput. Sci. 255 (2001), 152-162.
• [19] Néraud J. and C. Selmi, Locally complete sets and finite decomposable codes, Theoret. Comput. Sci. 273 (2002) 185-196.
• [20] Néraud J. and C. Selmi, Free monoid theory: Maximality and completeness in arbitrary submonoids, Int. Journ. of Alg. and Comp. 13 (5) (2003) 507-516.
• [21] Néraud J. and C. Selmi, A characterization of complete finite prefix codes in arbitrary submonoids of A_, Journ. of Aut. Langu. and Comb. 9 (2004) 103-110.
• [22] Pin J.E., Le problème de la synchronization. Contribution `a l'étude de la conjecture de Černỳ, Thèse de 3e cycle, Paris (1978).
• [23] Restivo A., Finitely generated sofic systems, Theoret. Comput. Sci. 65 (1989), 265-270.
• [24] Restivo A., Codes and local constraints, Theoret. Comput. Sci. 72 (1990), 55-64.
• [25] Restivo A., Salemi S. and T. Sportelli, Completing codes, Theoret. Info. and Appl. 23, 2 (1989), 135-147.
• [26] Sauer N. and M.G. Stone, Composing functions to reduce image size, Ars. Combin. 31 (1991) 171-176.