101. Pattern Matching with Variables: Fast Algorithms and New Hardness Results
- Author
-
Henning Fernau and Florin Manea and Robert Mercas and Markus L. Schmid, Fernau, Henning, Manea, Florin, Mercas, Robert, Schmid, Markus L., Henning Fernau and Florin Manea and Robert Mercas and Markus L. Schmid, Fernau, Henning, Manea, Florin, Mercas, Robert, and Schmid, Markus L.
- Abstract
A pattern (i. e., a string of variables and terminals) maps to a word, if this is obtained by uniformly replacing the variables by terminal words; deciding this is NP-complete. We present efficient algorithms\footnote{The computational model we use is the standard unit-cost RAM with logarithmic word size. Also, all logarithms appearing in our time complexity evaluations are in base 2.} that solve this problem for restricted classes of patterns. Furthermore, we show that it is NP-complete to decide, for a given number k and a word w, whether w can be factorised into k distinct factors; this shows that the injective version (i.e., different variables are replaced by different words) of the above matching problem is NP-complete even for very restricted cases.
- Published
- 2015
- Full Text
- View/download PDF