loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007)
Quantified Equality Constraints
Wroclaw, Poland
July 10-July 14
ISBN: 0-7695-2908-9
ASCII Text
x 
 
Manuel Bodirsky, Hubie Chen, "Quantified Equality Constraints," Logic in Computer Science, Symposium on, pp. 203-212, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), 2007.
 
 
BibTex
x
 
@article{ 10.1109/LICS.2007.38,
author = {Manuel Bodirsky and Hubie Chen},
title = {Quantified Equality Constraints},
journal ={Logic in Computer Science, Symposium on},
volume = {0},
year = {2007},
issn = {1043-6871},
pages = {203-212},
doi = {http://doi.ieeecomputersociety.org/10.1109/LICS.2007.38},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Logic in Computer Science, Symposium on
TI - Quantified Equality Constraints
SN - 1043-6871
SP203
EP212
A1 - Manuel Bodirsky,
A1 - Hubie Chen,
PY - 2007
KW - null
VL - 0
JA - Logic in Computer Science, Symposium on
ER -
 
Manuel Bodirsky, Humboldt-Universitat zu Berlin, Germany
Hubie Chen, Universitat Pompeu Fabra, Spain
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.
Citation:
Manuel Bodirsky, Hubie Chen, "Quantified Equality Constraints," lics, pp.203-212, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.