Assumption-based Pruning in Conditional CSP

Paper

“Assumption-based Pruning in Conditional CSP” is a 2005 paper by F. Geller and M. Veksler, published in the CP proceedings edited by Peter van Beek as Lecture Notes in Computer Science volume 3709, pages 241–255. The available evidence identifies it as the source for an assumption-based pruning scheme used with an extended MAC algorithm to improve pruning in conditional constraint satisfaction problems.

First seen 5/26/2026

Last seen 5/26/2026

Evidence 2 chunks

Wiki v1

WIKI

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.

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

1 connections

Assumption-based Pruning introduces → 100% 2e

The paper introduces assumption-based pruning for conditional CSPs.

CITATIONS

5 sources

5 citations — click to expand

[1] The paper was authored by F. Geller and M. Veksler and published in 2005 as “Assumption-based pruning in conditional CSP” in CP, Lecture Notes in Computer Science volume 3709, pages 241–255, Springer. [PDF] Constraint-Based Random Stimuli Generation for Hardware ... - AAAI

[2] The citing source describes conditional CSPs as problems where values assigned to some variables can make extensive parts of the CSP irrelevant, and gives an example in which the number of weakly coupled CSPs is itself a CSP variable. Constraint-Based Random Stimuli Generation for Hardware Verification

[3] The available evidence states that solving the conditional problems efficiently required extending the MAC algorithm and incorporating assumption-based pruning, citing Geller and Veksler 2005. Constraint-Based Random Stimuli Generation for Hardware Verification

[4] The evidence states that assumption-based pruning greatly enhances pruning under conditionality by simultaneously considering the state of all universes, each containing only a subset of the conditional sub-problems. Constraint-Based Random Stimuli Generation for Hardware Verification

[5] The citing AAAI paper presents IBM random stimuli generation for hardware verification as a complex application relying on AI techniques and notes continued exploration of CSP and knowledge-representation techniques. [PDF] Constraint-Based Random Stimuli Generation for Hardware ... - AAAI