Maintain-Arc-Consistency

Technique

Maintain-arc-consistency (MAC) is described in the evidence as a well-known constraint satisfaction problem solving scheme, associated with Mackworth 1977, and used as the overall algorithmic framework for a specialized solver in IBM's constraint-based random stimuli generation technology for hardware verification.

First seen 5/26/2026

Last seen 5/26/2026

Evidence 2 chunks

Wiki v1

WIKI

Overview

Maintain-arc-consistency (MAC) is a constraint-solving technique referenced as a well-known scheme for constraint satisfaction problems (CSPs). In the cited IBM hardware-verification work, MAC is the overall algorithmic framework of a specialized constraint solver for random stimuli generation. The paper identifies constraint propagation as the fundamental building block of MAC and notes that stochastic search is used in rare cases where constraint propagation is computationally hard.

Role in constraint-based random stimuli generation

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

Genesys PE ← implements 100% 2e

The CSP solver in Genesys PE adapts a maintain-arc-consistency scheme.

Genesys PE ← uses 100% 2e

Genesys PE's constraint solver is based on the MAC scheme.

Constraint Propagation ← part of 100% 1e

Constraint propagation is the fundamental building block of the MAC algorithm.

LINKED ENTITIES

3 links

Constraint Propagation building_block The evidence explicitly calls constraint propagation the fundamental building block of MAC.

Constraint Satisfaction Problem algorithmic_context The evidence states that maintain-arc-consistency is the overall algorithmic framework of a CSP solver and discusses MAC under the heading 'Constraint Satisfaction Problems.'

Stochastic Search fallback_when_propagation_is_hard The evidence states that stochastic search is used in rare cases where constraint propagation is computationally hard.

CITATIONS

8 sources

8 citations — click to expand

[1] MAC is identified as a well-known maintain-arc-consistency scheme associated with Mackworth 1977 and used as the overall algorithmic framework of a specialized constraint solver. [PDF] Constraint-Based Random Stimuli Generation for Hardware Verification - AAAI

[2] Constraint propagation is described as the fundamental building block of MAC, with stochastic search used when propagation is computationally hard. [PDF] Constraint-Based Random Stimuli Generation for Hardware Verification - AAAI

[3] IBM's stimuli-generation engine translates functional models, expert knowledge, and verification scenarios into constraints and adapts a maintain-arc-consistency scheme to stimuli generation. [PDF] Constraint-Based Random Stimuli Generation for Hardware Verification - AAAI

[4] CSPs are used in the cited system because they are declarative and support prioritization of expert-knowledge rules via Soft-CSP algorithms. [PDF] Constraint-Based Random Stimuli Generation for Hardware Verification - AAAI

[5] For random sampling, the described MAC-based solver randomizes all decisions in the search path, which prevents variable/value ordering heuristics and differs from regular MAC-based techniques. [PDF] Constraint-Based Random Stimuli Generation for Hardware Verification - AAAI

[6] The cited solver handles soft constraints in multi-tiered hierarchies and uses a local metric to balance soft-constraint satisfaction with diverse solution generation. [PDF] Constraint-Based Random Stimuli Generation for Hardware Verification - AAAI

[7] The cited stimuli-generation CSPs include variables with exponentially large domains, including address and data variables on the order of 2^32 or larger. [PDF] Constraint-Based Random Stimuli Generation for Hardware Verification - AAAI

[8] IBM reported more than $100 million in estimated savings over the prior decade from AI technology used for processor and system verification. [PDF] Constraint-Based Random Stimuli Generation for Hardware Verification - AAAI