Portal de Periódicos da CAPES

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

2012; IOS Press; Volume: 116; Issue: 1-4 Linguagem: Inglês

10.3233/fi-2012-680

1875-8681

Narad Rampersad, Jeffrey Shallit, Zhi Xu,

DNA and Biological Computing

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