Assumption-based Pruning

Concept

Assumption-based pruning is a pruning scheme used for conditional constraint satisfaction problems (CSPs). In IBM's constraint-based random stimuli generation work for hardware verification, it was incorporated into an extension of the MAC algorithm to improve pruning when parts of a CSP become relevant or irrelevant depending on variable assignments.

First seen 5/26/2026

Last seen 5/26/2026

Evidence 2 chunks

Wiki v1

WIKI

Overview

Assumption-based pruning is a pruning scheme associated with conditional constraint satisfaction problems (CSPs). In the cited IBM hardware-verification application, many CSP instances were described as conditional: depending on the value assigned to some variables, extensive parts of the CSP may become irrelevant. The authors state that they extended the MAC algorithm and incorporated assumption-based pruning to solve such conditional problems efficiently. [C1]

Role in conditional CSPs

READ FULL ARTICLE →

NEIGHBORHOOD

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

explore full graph →

RELATIONSHIPS

3 connections

Assumption-based Pruning in Conditional CSP ← introduces 100% 2e

The paper introduces assumption-based pruning for conditional CSPs.

Genesys PE ← uses 100% 1e

Genesys PE extends the MAC algorithm with assumption-based pruning to handle conditional CSPs.

Conditional CSP ← uses 100% 1e

Assumption-based pruning is employed to handle conditional CSPs efficiently.

LINKED ENTITIES

2 links

Conditional CSP used_in The evidence explicitly identifies assumption-based pruning as being incorporated to solve conditional problems and cites 'Assumption-based pruning in conditional CSP.'

Constraint Satisfaction Problem applies_to The evidence discusses conditional CSPs and CSP variables in the context where assumption-based pruning is used.

CITATIONS

6 sources

6 citations — click to expand

[1] Assumption-based pruning was incorporated into an extension of the MAC algorithm to solve conditional CSP problems efficiently. Constraint-Based Random Stimuli Generation for Hardware Verification

[2] Conditional problems are described as CSPs where variable assignments can make extensive parts of the CSP irrelevant; examples include weakly coupled CSPs where the number of sub-CSPs is itself a CSP variable. Constraint-Based Random Stimuli Generation for Hardware Verification

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

[4] IBM's random stimuli generation for hardware verification is presented as a complex application relying on AI techniques, with ongoing exploration of CSP and knowledge-representation techniques. Constraint-Based Random Stimuli Generation for Hardware Verification

[5] Genesys PE is described as a stimuli generator for processor and multi-processor verification and as the major functional verification tool for IBM PowerPC processor designs since 2000. Constraint-Based Random Stimuli Generation for Hardware Verification

[6] The reference list cites Geller and Veksler's 2005 paper 'Assumption-based pruning in conditional CSP' in CP, LNCS volume 3709, pages 241–255, Springer. Constraint-Based Random Stimuli Generation for Hardware Verification