A Characterisation of First-Order Constraint Satisfaction Problems

Seattle, Washington August 12-August 15

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/LICS.2006.6

21st Annual IEEE Symposium on Logic i ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Benoit Larose Articles by Cynthia Loten Articles by Claude Tardif

	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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.