DocumentCode
2510424
Title
A Characterisation of First-Order Constraint Satisfaction Problems
Author
Larose, Benoit ; Loten, Cynthia ; Tardif, Claude
Author_Institution
Dept. of Math. & Stat., Concordia Univ., Montreal, Que.
fYear
0
fDate
0-0 0
Firstpage
201
Lastpage
210
Abstract
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
Keywords
computational complexity; constraint theory; decidability; relational algebra; NP-complete problem; decidability; finite relational core structures; first-order constraint satisfaction problem characterisation; near-unanimity functions; polynomial-time algorithm; Character recognition; Combinatorial mathematics; Computer science; Constraint theory; Educational institutions; Graph theory; Logic; Polynomials; Relational databases; Statistics;
fLanguage
English
Publisher
ieee
Conference_Titel
Logic in Computer Science, 2006 21st Annual IEEE Symposium on
Conference_Location
Seattle, WA
ISSN
1043-6871
Print_ISBN
0-7695-2631-4
Type
conf
DOI
10.1109/LICS.2006.6
Filename
1691231
Link To Document