The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages

• Autorzy: Rampersad N. , Shallit J. , Xu Z.
• Języki publikacji: EN

Abstrakty

EN

In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Σ*? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černy, and Restivo's conjecture on the minimal uncompletable word.

Słowa kluczowe

EN

prefix; suffix; factor; subword; universality; PSPACE-complete problem; decision problem; polynomial time; synchronizing word; synchronizing automaton; Restivo's conjecture

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 223--236
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Rampersad N.

autor

Shallit J.

autor

Xu Z.

• School of Computer Science, University of Waterloo Waterloo, Ontario N2L 3G1, Canada,

Bibliografia

• [1] Bar-Hillel, Y., Perles,M., Shamir, E.: On formal properties of simple phrase structure grammars, Z. Phonetik. Sprachwiss. Kommunikationsforsch., 14, 1961, 143-172.
• [2] Fici, G., Pribavkina, E., Sakarovitch, J.: On the minimal uncompleteable word problem, 2010, Available at http://arxiv.org/abs/1002.1928.
• [3] Gusev, V. V., Pribavkina, E. V.: On non-complete sets and Restivo's conjecture, in: Developments in Language Theory, 15th International Conference, DLT 2011 (G. Mauri, A. Leporati, Eds.), vol. 6795 of Lect. Notes in Comp. Sci., Springer, 2011, 239-250.
• [4] Hartmanis, J.: Context-free languages and Turing machine computations, in: Mathematical Aspects of Computer Science, vol. 19 of Proc. Symp. Appl. Math., American Mathematical Society, 1967, 42-51.
• [5] Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata, in: LATA 2009 (A. H. Dediu, A. M. Ionescu, C. Mart´ın-Vide, Eds.), vol. 5457 of Lect. Notes in Comp. Sci., Springer, 2009, 23-42.
• [6] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
• [7] Hunt III, H. B., Rosenkrantz, D. J., Szymanski, T. G.: On the equivalence, containment, and covering problems for the regular and context-free languages, J. Comput. System Sci., 12, 1976, 222-268.
• [8] Julia, S.: Minimal uncompletable words, 2011, Presented at the 1st Russian-Finnish Symposium on Discrete Mathematics, St. Petersburg, Russia, September 21-24, 2011.
• [9] Kao, J.-Y., Rampersad, N., Shallit, J.: On NFAs where all states are final, initial, or both, Theoret. Comput. Sci., 410, 2009, 5010-5021.
• [10] Kao, J.-Y., Shallit, J., Xu, Z.: The Frobenius problem in a free monoid, in: 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008) (S. Albers, P. Weil, Eds.), vol. 1 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2008, 421-432, Available at http://drops.dagstuhl.de/opus/volltexte/2008/1362.
• [11] Knuth, D. E.: The Art of Computer Programming: Volume 3, Sorting and Searching, Addison-Wesley, 1997.
• [12] Kozen, D.: Lower bounds for natural proof systems, in: Proc. 18th Symp. Found. Comput. Sci. (FOCS), IEEE Society Press, 1977, 254-266.
• [13] Martugin, P. V.: A series of slowly synchronizing automata with a zero state over a small alphabet, Info. Comput., 206, 2008, 1197-1203.
• [14] Meyer, A. R., Stockmeyer, L. J.: The equivalence problem for regular expressions with squaring requires exponential space, in: Proc. 13th Ann. IEEE Symp. on Switching and Automata Theory, 1972, 125-129.
• [15] Néraud, J., Selmi, C.: On codes with a finite deciphering delay: constructing uncompletable words, Theoret. Comput. Sci., 255, 2001, 151-162.
• [16] Paterson, M. S.: Unsolvability in 3 ﾗ 3 matrices, Studies in Appl. Math., 49, 1970, 105-107.
• [17] Pribavkina, E. V.: Slowly synchronizing automata with zero and incomplete sets, 2009, Available at http://arxiv.org/abs/0907.4576.
• [18] Restivo, A.: Some remarks on complete subsets of a free monoid, Quaderni de "La ricerca Scientifica", CNR Roma 109, 1981, 19-25.
• [19] Rystsov, I.: Reset words for commutative and solvable automata, Theoret. Comput. Sci., 172, 1997, 273-279.
• [20] Shallit, J.: Universality and prefixes, suffixes, and factors, Invited talk for the WORDS 2009 conference, Salerno, Italy, September 15 2009.
• [21] Tarjan, R.: Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 1972, 146-160.
• [22] Volkov, M. V.: Synchronizing words and the ˇCern´y conjecture, in: LATA 2008 (C. Mart´ın-Vide, F. Otto, H. Fernau, Eds.), vol. 5196 of Lect. Notes. in Comp. Sci., Springer, 2008, 11-27.