Variable Dependencies of Quantified CSPs (bibtex)

by Marko Samer

Abstract:

Quantified constraint satisfaction extends classical constraint satisfaction by a linear order of the variables and an associated existential or universal quantifier to each variable. In general, the semantics of the quantifiers does not allow to change the linear order of the variables arbitrarily without affecting the truth value of the instance. In this paper we investigate variable dependencies that are caused by the influence of the relative order between these variables on the truth value of the instance. Several approaches have been proposed in the literature for identifying such dependencies in the context of quantified Boolean formulas. We generalize these ideas to quantified constraint satisfaction and present new concepts that allow a refined analysis.

Reference:

Variable Dependencies of Quantified CSPsMarko SamerProceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR'08), volume 5330 of Lecture Notes in Computer Science, pages 512-527, 2008, Springer-Verlag.

Bibtex Entry:

@inproceedings{Sam08LPAR, author = {Marko Samer}, title = {Variable Dependencies of Quantified CSPs}, year = {2008}, booktitle = {Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR'08)}, pages = {512--527}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {5330}, abstract = {Quantified constraint satisfaction extends classical constraint satisfaction by a linear order of the variables and an associated existential or universal quantifier to each variable. In general, the semantics of the quantifiers does not allow to change the linear order of the variables arbitrarily without affecting the truth value of the instance. In this paper we investigate variable dependencies that are caused by the influence of the relative order between these variables on the truth value of the instance. Several approaches have been proposed in the literature for identifying such dependencies in the context of quantified Boolean formulas. We generalize these ideas to quantified constraint satisfaction and present new concepts that allow a refined analysis.}, isbn = {978-3-540-89438-4}, doi = {10.1007/978-3-540-89439-1_36} }

Powered by bibtexbrowser