A Characterisation of First-Order Constraint Satisfaction Problems

We characterise finite relational core structures admitting finitely many obstructions, in terms of special near unanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first...

Full description

Saved in:
Bibliographic Details
Main Authors: Larose, B., Loten, C., Tardif, C.
Format: Conference Proceeding
Language:English
Subjects:
Character recognition
Combinatorial mathematics
Computer science
Constraint theory
Educational institutions
Graph theory
Logic
Polynomials
Relational databases
Statistics
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We characterise finite relational core structures admitting finitely many obstructions, in terms of special near unanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores
ISSN:1043-6871
2575-5528
DOI:10.1109/LICS.2006.6