  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 Sigma is the set of all prefixes (resp., suffixes, factors, subwords)
of all words of L equal to Sigma*? In the case of testing universality for
factors of languages represented by DFA's, we find an interesting connection to
Cerny's conjecture on synchronizing words.
