The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages
Title:
The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages
Author:
Rampersad, Narad Shallit, Jeffrey Xu, Zhi
Appeared in:
Fundamenta informaticae
Paging:
Volume 116 (2012) nr. 1-4 pages 223-236
Year:
2012-05-16
Contents:
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.