Output details
11 - Computer Science and Informatics
University of Hertfordshire
Return to search
Output 0 of 0 in the submission
Article title
CSP duality and trees of bounded pathwidth
Type
D - Journal article
Title of journal
Theoretical Computer Science
Article number
-
Volume number
411
Issue number
34-36
First page of article
3188
ISSN of journal
0304-3975
Year of publication
2010
URL
-
Number of additional authors
2
Additional information
<10> The study of Constraint Satisfaction problems (CSPs) definable in various fragments of the logic programming language Datalog has recently gained considerable importance. We fully characterise CSPs defined in a widely used fragment of Datalog, connecting algebra, combinatorics, logic and theoretical computer science in a natural way.
This was a major contribution to the descriptive complexity of tractable CSPs, inspired a grant application, and its results were used by other researchers (Montreal, Canada) to obtain a full classification for the List Homomorphism Problems for graphs. This paper is a result of an ongoing collaboration with researchers at Durham and Barcelona.
Interdisciplinary
Yes
Cross-referral requested
-
Research group
None
Citation count
2
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
