Manuel Bodirsky

Collapsibility in Infinite-Domain Quantified Constraint Satisfaction

With Hubie Chen. In the proceedings of the 5th EACSL Annual Conference on Computer Science and Logic (CSL06)

Abstract

In this article, we study the quantified constraint satisfaction problem (QCSP) over infinite domains. We develop a technique called collapsibility that allows one to give strong complexity upper bounds on the QCSP. This technique makes use of both logical and universal-algebraic ideas. We give applications illustrating the use of our technique.

Download

in pdf.


last modified 05/07 (Manuel Bodirsky)