Affiliations: Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba R3B 2E9, Canada, [email protected] | School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada, [email protected]; [email protected]
Note: [] Address for correspondence: Google Inc., 151 Charles Street W., Suite 200, Kitchener, Ontario, N2G 1H6, Canada
Abstract: 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 Černý, and Restivo's conjecture on the minimal uncompletable word.
Keywords: prefix, suffix, factor, subword, universality, PSPACE-complete, decision problem, polynomial time, synchronizing word, synchronizing automaton, Restivo's conjecture
