You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: University of Hertfordshire » Outputs » Detail

Output details

11 - Computer Science and Informatics

University of Hertfordshire

Return to search Previous output Next output

Output 33 of 109 in the submission

Article title

CSP duality and trees of bounded pathwidth

Type

D - Journal article

DOI

10.1016/j.tcs.2010.05.016

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

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

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract