Thumbnail
Access Restriction
Open

Author Chen, Hubie
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Unify Exist-ing Tractability Result ♦ General Framework ♦ Tractable Qcsps ♦ Certain Case ♦ Correspond-ing Algorithm ♦ New Class ♦ Quantified Constraint Satisfaction Problem ♦ Con-straint Satisfaction Problem ♦ Quantified Constraint Satisfaction ♦ Uniform Fash-ion ♦ Polynomial-time Tractability
Description The concept of consistency has pervaded studies of the con-straint satisfaction problem. We introduce two concepts, which are inspired by consistency, for the more general framework of the quantified constraint satisfaction problem (QCSP). We use these concepts to derive, in a uniform fash-ion, proofs of polynomial-time tractability and correspond-ing algorithms for certain cases of the QCSP where the types of allowed relations are restricted. We not only unify exist-ing tractability results and algorithms, but also identify new classes of tractable QCSPs.
In Proceedings of AAAI-04
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2004-01-01