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
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2006.6
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||