Consistency for quantified constraint satisfaction problems

P Nightingale

Research output: Book/ReportBook

6 Citations (Scopus)

Abstract

The generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems arising in AI, such as reasoning with uncertainty, and multiplayer games. I define two new levels of consistency for QCSP, and give an algorithm to enforce consistency for one of these definitions. The algorithm is embedded in backtracking search, and tested empirically. The aims of this work are to increase the facilities available for modelling and to increase the power of constraint propagation for QCSPs. The work is motivated by examples from adversarial games.

Original languageEnglish
PublisherUnknown Publisher
Number of pages5
Publication statusPublished - 2005

Fingerprint

Dive into the research topics of 'Consistency for quantified constraint satisfaction problems'. Together they form a unique fingerprint.

Cite this