
Quantified Constraint Satisfaction Problems (QCSP) are a generalization of Constraint Satisfaction Problems (CSP) in which variables may be quantified existentially and universally. QCSP offers a natural framework to express PSPACE problems as finite two-player games or planning under uncertainty. State-of-the-art QCSP solvers have an important drawback: they explore much larger combinatorial spaces than the natural search space of the original problem since they are unable to recognize that some sub-problems are necessarily true. We introduce a new tool, inspired by the cut rule of Prolog as a tool under responsibility of the designer of the QCSP, to prune those parts of the search space which are by construction known to be useless. We use this new tool to restore on one hand the annihilator property of true for disjunction in QCSP solver and, on the other hand, to prune the search space in two-player games. It is a simple solution to use efficiently QCSP to design finite two-player games without restricting the QCSP language. This tool does not need to modify the QCSP solver but has only one requirement: be able to tell the QCSP solver that the current QCSP is solved. Our QCSP solver built over Ge Code, a CSP library, obtained very good results compared to state-of-the-art QCSP solvers.
[INFO] Computer Science [cs]
[INFO] Computer Science [cs]
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
