In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. Several such conditions exist, the most known being node consistency, arc consistency, and path consistency. Local consistency can be enforced via transformations of the problem called constraint propagation.
Local consistency conditions can be grouped into various classes. The original local consistency conditions require that every consistent assignment can be consistently extended to another variable. Directional consistency only requires this condition to be satisfied when the other variable is higher than the ones in the assignment, according to a given order. Relational consistency includes extensions to more than one variable, but this extension is only required to satisfy a given constraint or set of constraints.
Every local consistency condition can be enforced by a transformation that changes the problem without changing its solutions. Such a transformation is called constraint propagation. Constraint propagation works by reducing domains of variables, strengthening constraints, or creating new ones. This leads to a reduction of the search space, making the problem easier to solve by some algorithms. Constraint propagation can also be used as an unsatisfiability checker, incomplete in general but complete in some particular cases.
Read more about Local Consistency: Assumptions, Local Consistency, Directional Consistency, Relational Consistency, Uses of Local Consistency
Famous quotes containing the words local and/or consistency:
“Civility, which is a disposition to accommodate and oblige others, is essentially the same in every country; but good breeding, as it is called, which is the manner of exerting that disposition, is different in almost every country, and merely local; and every man of sense imitates and conforms to that local good breeding of the place which he is at.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“People who love only once in their lives are ... shallow people. What they call their loyalty, and their fidelity, I call either the lethargy of custom or their lack of imagination. Faithfulness is to the emotional life what consistency is to the life of the intellect—simply a confession of failures.”
—Oscar Wilde (1854–1900)