Generalized arc consistency

From Glossary

Jump to: navigation, search


An extension of arc consistency to constraints with more than two variables in their scope.

A variable LaTeX: x is generalized arc consistent (GAC) with a constraint if every value of the variable can be extended to all the other variables of the constraint in such a way the constraint is satisfied.

Generalized arc consistency is one of the most commonly enforced forms of consistency in constraint programming.

GAC has also been called: hyper-arc consistency and domain consistency.


Arc consistencybutton.png

A consistency property in constraint programming used as a basis for inference. A variable LaTeX: x is arc-consistent with another variable LaTeX: y if for every value in the domain of LaTeX: x there exists a value in the domain of LaTeX: y such that the binary constraint LaTeX: C(x,y) is satisfied. A binary constraint LaTeX: C(x,y) is arc-consistent if both of its variables are arc-consistent with respect to each other.

See also:


Views
Personal tools