Patterns with bounded treewidth

2012-03-27T10:46:38Z (GMT) by Daniel Reidenbach Markus L. Schmid
We show that any parameter of patterns that is an upper bound for the treewidth of appropriate encodings of patterns as relational structures, if restricted to a constant, allows the membership problem for pattern languages to be solved in polynomial time. Furthermore, we identify a new such parameter, called the scope coincidence degree.