The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages
Narad Rampersad, Jeffrey O. Shallit, Zhi Xia Xu · Fundamenta Informaticae · 2012
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 t