loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)
A Characterisation of First-Order Constraint Satisfaction Problems
Seattle, Washington
August 12-August 15
ISBN: 0-7695-2631-4
ASCII Text
x 
 
Benoit Larose, Cynthia Loten, Claude Tardif, "A Characterisation of First-Order Constraint Satisfaction Problems," Logic in Computer Science, Symposium on, pp. 201-210, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/LICS.2006.6,
author = {Benoit Larose and Cynthia Loten and Claude Tardif},
title = {A Characterisation of First-Order Constraint Satisfaction Problems},
journal ={Logic in Computer Science, Symposium on},
volume = {0},
year = {2006},
issn = {1043-6871},
pages = {201-210},
doi = {http://doi.ieeecomputersociety.org/10.1109/LICS.2006.6},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Logic in Computer Science, Symposium on
TI - A Characterisation of First-Order Constraint Satisfaction Problems
SN - 1043-6871
SP201
EP210
A1 - Benoit Larose,
A1 - Cynthia Loten,
A1 - Claude Tardif,
PY - 2006
KW - null
VL - 0
JA - Logic in Computer Science, Symposium on
ER -
 
Benoit Larose, Concordia University, Canada
Cynthia Loten, Royal Military College of Canada, Canada
Claude Tardif, Royal Military College of Canada, Canada
We characterise finite relational core structures admitting finitely many obstructions, in terms of special nearunanimity 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.
Citation:
Benoit Larose, Cynthia Loten, Claude Tardif, "A Characterisation of First-Order Constraint Satisfaction Problems," lics, pp.201-210, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.