Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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].
Wydawca
Czasopismo
Rocznik
Tom
Strony
549--562
Opis fizyczny
bibliogr. 26 poz.
Twórcy
autor
- 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, Jean.neraud@univ-rouen.fr
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0016-0003