# Matching Patterns with Variables

Florin Manea ( Kiel University )

- 11:00 26th October 2018 ( week 3, Michaelmas Term 2018 )Room 441

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.