Matching Patterns with Variables

A pattern $\alpha$ (i.e., a string of variables and terminals) matches
a word $w$, if $w$ can be obtained by uniformly replacing the
variables of $\alpha$ by terminal words. The respective matching
problem, i.e., deciding whether or not a given pattern matches a given
word, is generally NP-complete, but can be solved in polynomial-time
for restricted classes of patterns. We present a series of efficient
algorithms for the matching problem for such restricted patterns,
e.g., patterns with a bounded number of repeated variables, or
patterns with structural restrictions on the order of variables.