Overview

“Assumption-based Pruning in Conditional CSP” is a paper by F. Geller and M. Veksler, published in 2005 in the CP proceedings edited by Peter van Beek, as Lecture Notes in Computer Science volume 3709, pages 241–255, by Springer.

The paper is cited in an AAAI 2006 article on constraint-based random stimuli generation for hardware verification as the reference for incorporating assumption-based pruning into an extended MAC algorithm for conditional constraint satisfaction problems.

Problem setting

The cited application context describes many constraint satisfaction problems as conditional: depending on the value assigned to some variables, extensive parts of the CSP may become irrelevant. The same source notes that such conditional problems also occur in other applications such as manufacturing configuration, but emphasizes a hardware-verification variant in which a full problem may consist of several weakly coupled CSPs and the number of those CSPs can itself be a CSP variable.

Technique as described in the available evidence

The available evidence states that, to solve these conditional problems efficiently, the authors of the hardware-verification system had to extend the MAC algorithm and incorporate assumption-based pruning, citing Geller and Veksler’s 2005 paper. The described benefit is stronger pruning under conditionality: the scheme “simultaneously takes into account the state of all universes,” where each universe contains only a certain subset of the conditional sub-problems.

Application context in the evidence

The citing AAAI paper discusses IBM random stimuli generation for hardware verification as a complex application relying on AI techniques, including CSP and knowledge-representation methods. Within that context, assumption-based pruning is presented as one of the techniques needed for conditional CSPs in processor and system verification problems.