Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-28332-1_40 | Information & Computation |
Keywords | DocType | Volume |
membership problem,relational structure,bounded treewidth,pattern language,polynomial time,scope coincidence degree,appropriate encodings,treewidth | Conference | 239 |
ISSN | Citations | PageRank |
0890-5401 | 6 | 0.50 |
References | Authors | |
22 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Reidenbach | 1 | 154 | 18.06 |
| Markus L. Schmid | 2 | 93 | 15.93 |