Computational complexity of generalized pattern matching
Christine Heitsch, John Rhodes · 2000
We consider a generalization of the standard pattern matching quest primarily through the decision problem associated with the asymptotic case. This is accomplished using the theory of unavoidable patterns and their characterization in terms of Zimin words and suitably constructed sequences of deletions. Although many efficient algorithms already exist for standard string searching in the exact and approximate cases, the special case of generalized pattern matching concerning the occurrence of unavoidable patterns in Zimin words does not appear so tractable. Specifically, we provide an exponential lower bound to any algorithmic approach which relies exclusively on the deletion criteria to determine pattern unavoidability. Also, it is shown that all combinations and extensions of the other known necessary conditions are not sufficient to decide unavoidability. Thus, like the graph isomorphism problem for which an NP-completeness proof also remains elusive, the special case of generalized pattern matching involving deciding pattern unavoidability is known to be in NP and is currently expected not to succumb to any polynomial time algorithm.