Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twenty-First Annual IEEE Symposium on

Logic in Computer Science (LICS 2006)

Paper: A Characterisation of First-Order Constraint Satisfaction Problems (at LICS 2006)

Authors: Benoit Larose Cynthia Loten Claude Tardif

Abstract

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.

BibTeX

  @InProceedings{LaroseLotenTardif-ACharacterisationof,
    author = 	 {Benoit Larose and Cynthia Loten and Claude Tardif},
    title = 	 {A Characterisation of First-Order Constraint Satisfaction Problems},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {201--210},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2017-04-0512:37
Andrzej Murawski