On the computational and descriptional complexity of multi-pattern languages

We study the complexity of a restricted version of the universality problem: testing equivalence to { 0 , 1 } ⁎ for languages that are either { 0 , 1 } ⁎ or { 0 , 1 } ⁎ − { w } where w ∈ { 0 , 1 } ⁎ . We show that this restricted problem for multi-pattern languages (MPL) is NP-hard, and for multi-pattern languages with regular substitutions (MPL REG ) is not recursively enumerable. Moreover, this undecidability result holds for any class of languages that effectively contains { w # w | w ∈ { 0 , 1 } ⁎ } , and is effectively closed under union, and concatenation with regular sets. Consequently, it has broad applicability and extends to many generalizations of regular languages. Sufficient conditions are then presented for a language predicate to be as hard as the restricted universality problem. By applying these conditions, we develop a uniform method for showing undecidability and complexity results simultaneously via highly efficient many-one reductions. In addition, the properties of this restricted universality problem can be used to investigate the descriptional complexity of multi-patterns. We show that the trade-off between multi-patterns and regular expressions is not exponential-size bounded. Non-recursive trade-offs between multi-patterns (or multi-patterns with regular substitutions) and numerous classes of language descriptors are also established.