Computing forbidden words of regular languages

• Autorzy: Béal M-P. , Crochemore M. , Mignosi F. , Restivo A. , Sciortino M.
• Języki publikacji: EN

Abstrakty

EN

We give a quadratic-time algorithm to compute the set of minimal forbidden words of a factorial regular language. We give a linear-time algorithm to compute the minimal forbidden words of a finite set of words. This extends a previous result given for the case of a single word only. We also give quadratic-time algorithms to check whether a regular language is factorial or anti-factorial.

Słowa kluczowe

EN

anti-factorial language; factor automaton; factorial language; failure function; forbidden word; formal languages; sofic shift; symbolic dynamics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 56, nr 1,2
• Strony: 121--135
• Opis fizyczny: wykr., bibliogr. 15 poz.

Twórcy

autor

Béal M-P.

autor

Crochemore M.

autor

Mignosi F.

autor

Restivo A.

autor

Sciortino M.

• Institut Gaspard-Monge, Université de Marne-la-Vallée, 77454 Marne-la-Vallée Cedex 2, France,

Bibliografia

• 1] B´eal, M.-P., Mignosi, F., Restivo, A., Sciortino, M.: Forbidden words in symbolic dynamics, Adv. in Appl. Math., 25(2), 2000, 163-193.
• [2] B´eal, M.-P., Senellart, J.: On the bound of the synchronization delay of a local automaton, Theoret. Comput. Sci., (205), 1998, 297-306.
• [3] Blumer, A., Blumer, J., Haussler, D., McConnell, R., Ehrenfeucht, A.: Complete Inverted Files for Efficient Text Retrieval and Analysis, Journal of the ACM, 34(3), 1987, 578-595.
• [4] Carpi, A., de Luca, A., Varricchio, S.: Words, univalent factors and boxes, Acta Informatica, 38(6), 2002, 409-436.
• [5] ˇCern´y, J.: Pozn´amka k. homog´ennym experimentom s koneˇcn´ymi automatmi, Mat. fyz. ˇcas., SAV 14, 1964, 208-215.
• [6] Crochemore, M., Hancart, C., Lecroq, Th.: Algorithmique du Texte, Vuibert, Paris, 2001.
• [7] Crochemore, M., Mignosi, F., Restivo, A.: Automata and forbidden words, Inform. Process. Lett., 67, 1998, 111-117.
• [8] Crochemore, M., Mignosi, F., Restivo, A., Salemi, S.: Data compression using antidictionaries, in: Proceedings of the IEEE, Lossless Data Compression (J. Storer, Ed.), 2000, 1756-1768.
• [9] Davenport, J. H.: Computer algebra for cylindrical algebraic decomposition, 1985, TRITA-NA-8511, NADA, KTH, Stockholm.
• [10] Davenport, J. H., Siret, Y., Tournier, E.: Computer Algebra, Second edition, Academic Press Ltd., London, 1993, Systems and algorithms for algebraic computation, With a preface by Daniel Lazard, Translated from the French by A. Davenport and J. H. Davenport, With a foreword by Anthony C. Hearn.
• [11] Hopcroft, J. E., Montwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, second edition, Addison-Wesley, 2001.
• [12] Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.
• [13] Mignosi, F., Restivo, A., Sciortino, M.: Forbidden factors in finite and infinite words, in: Jewels are Forever, Springer, Berlin, 1999, 339-350.
• [14] Mignosi, F., Restivo, A., Sciortino, M.: Forbidden Factors and Fragment Assembly, RAIRO Theoret. Inform. Appl., 35(6), 2001, 565-577, (Journal version).
• [15] Raffinot, M.: Structures pour la localisation de motifs, Ph.D. Thesis, University of Marne-la-Vall´ee, France, 1999.