Name
Abstract | ||
|---|---|---|
We characterize obstruction sets in caterpillar dualities in terms of regular languages and give a construction of the dual of a regular family of caterpillars. In particular, we prove that every monadic linear Datalog program with at most one extensional database per rule defines the complement of a contraint satisfaction problem. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/120879270 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
constraint satisfaction problems,caterpillar duality,regular languages | Journal | 27 |
Issue | ISSN | Citations |
3 | 0895-4801 | 1 |
PageRank | References | Authors |
0.40 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Péter L. Erdös | 1 | 267 | 46.75 |
| Claude Tardif | 2 | 341 | 38.08 |
| Gábor Tardos | 3 | 1261 | 140.58 |