%0 Journal Article %A Reidenbach, Daniel %A Schmid, Markus L. %D 2012 %T Patterns with bounded treewidth %U https://repository.lboro.ac.uk/articles/journal_contribution/Patterns_with_bounded_treewidth/9402710 %2 https://repository.lboro.ac.uk/ndownloader/files/17019287 %K Pattern languages %K Membership problem %K Treewidth %K Extended regular expressions %K Information and Computing Sciences not elsewhere classified %X 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. %I Loughborough University