Maintaining Arc Consistency
TechniqueMaintaining arc consistency (MAC) is a family of constraint-satisfaction algorithms that uses arc consistency as a filtering mechanism. In the cited Genesys-Pro test-program generation work, a customized MAC solver reduces variable domains through mandatory and nonmandatory constraints, reaches fixed points, and uses random single-value selections until a full satisfying assignment is produced.
First seen 5/26/2026
Last seen 6/14/2026
Evidence 5 chunks
Wiki v1
WIKI
Overview
Maintaining arc consistency (MAC) is described as a family of algorithms that uses arc consistency as its filtering mechanism. An arc is arc-consistent when, for any value in the domain of any variable in the arc, there is a valid assignment to the other variables in the arc that satisfies the constraint. The procedure for reaching arc consistency removes from variable domains the values that cannot participate in any solution. [C1]
Role in constraint-satisfaction problems
NEIGHBORHOOD
No graph connections found for this entity yet. It may appear in future ingestion runs.
explore full graph →RELATIONSHIPS
2 connectionsGenesys-Pro uses a MAC-based algorithm as its CSP solver
Maintaining arc consistency is a family of algorithms within constraint satisfaction
CITATIONS
13 sources13 citations — click to expand
[1] C1: MAC is a family of algorithms using arc consistency as a filtering mechanism, and arc consistency removes domain values that cannot participate in any solution. [PDF] Genesys-pro: innovations in test program generation for functional ...
[2] C2: A CSP consists of variables, domains, and constraints; a solution assigns values satisfying all constraints; a constraint graph represents variables as nodes and constraints as arcs. [PDF] Genesys-pro: innovations in test program generation for functional ...
[3] C3: Test-program generation CSPs can have very large domains, including 2^32-sized domains for 32-bit register data and address attributes, making strong filtering mechanisms useful. [PDF] Genesys-pro: innovations in test program generation for functional ...
[4] C4: Genesys-Pro uses an external generic solver implementing a customized MAC algorithm for pseudorandom test-program generation, producing uniformly distributed random solutions satisfying all mandatory constraints and as many nonmandatory constraints as possible. [PDF] Genesys-pro: innovations in test program generation for functional ...
[5] C5: The MAC procedure first applies arc consistency over mandatory constraints and fails if a mandatory constraint cannot reach arc consistency. [PDF] Genesys-pro: innovations in test program generation for functional ...
[6] C6: The MAC procedure applies arc consistency to nonmandatory constraints in priority order, ignores failures, reconsiders mandatory constraints, and repeats until a fixed point is reached. [PDF] Genesys-pro: innovations in test program generation for functional ...
[7] C7: After reaching a fixed point, the algorithm randomly selects one variable and reduces its domain to a single element, retriggering arc consistency. [PDF] Genesys-pro: innovations in test program generation for functional ...
[8] C8: The algorithm reaches a solution after each variable domain is reduced to a single element. [PDF] Genesys-pro: innovations in test program generation for functional ...
[9] C9: A single instruction is generated by formulating the request as a CSP, solving it to produce an instruction instance satisfying constraints, and invoking the architecture reference model for simulation. [PDF] Genesys-pro: innovations in test program generation for functional ...
[10] C10: Genesys-Pro formulates instruction CSPs by mapping instruction attributes to variables and architectural or testing-knowledge constraints to arcs, including base.address != target.address. [PDF] Genesys-pro: innovations in test program generation for functional ...
[11] C11: In the Load-instruction example, fixed point 0 eliminates value 5 from base.address and reduces source.address to quad-word-aligned addresses represented as 0xXXXXXXX0. [PDF] Genesys-pro: innovations in test program generation for functional ...
[12] C12: MAC-based algorithms are presented as well suited to test-program generation because they postpone heuristic decisions until after considering architectural and testing-knowledge constraints. [PDF] Genesys-pro: innovations in test program generation for functional ...
[13] C13: The source states that local-heuristic early pruning can weaken the ability to solve several constraints simultaneously and explore the search space uniformly. [PDF] Genesys-pro: innovations in test program generation for functional ...