Paper: Quantified Equality Constraints (at LICS 2007)

Authors: Manuel Bodirsky Hubie Chen

Abstract

An equality template (also equality constraint language) is a relational structure with infinite universe whose relations can be defined by boolean combinations of equalities. We prove a complete complexity classification for quantified constraint satisfaction problems (QCSPs) over equality templates: these problems are in L (decidable in logarithmic space), NP-complete, or PSPACE-complete. To establish our classification theorem we combine methods from universal algebra with concepts from model theory.

BibTeX

  @InProceedings{BodirskyChen-QuantifiedEqualityC,
    author = 	 {Manuel Bodirsky and Hubie Chen},
    title = 	 {Quantified Equality Constraints},
    booktitle =  {Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007)},
    year =	 {2007},
    month =	 {July}, 
    pages =      {203--212},
    location =   {Wroclaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }