| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428675 | Information Processing Letters | 2010 | 5 Pages |
Abstract
We consider some natural variations on the following classic pattern-matching problem: given an NFA M over the alphabet Σ and a pattern p over some alphabet Δ, does there exist a word x∈L(M) such that x matches p? We consider the restricted problem where M only accepts a finite language. We also consider the variation where only some factor of x is required to match the pattern p. We show that both of these problems are NP-complete. We also consider the same problems for context-free grammars; in this case the problems become PSPACE-complete.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
