K-consistency

From Glossary

Jump to: navigation, search


A consistency notion in constraint programming.

Let LaTeX: P = (X, D, C) be a CSP.

  • Given a set of variables LaTeX: Y \subseteq X with LaTeX: |Y| = k -1 , a locally consistent instantiation LaTeX: I on LaTeX: Y is k-consistent iff for any kth variable LaTeX: x_{i_{k}} \in X \setminus Y there exists a value LaTeX: v_{i_{k}} \in D(x_{i_{k}}) such that LaTeX: I \cap \{ (x_{i_k}, v_{i_k}) \} is locally consistent.
  • The CSP LaTeX: P is k-consistent iff for any set LaTeX: Y of LaTeX: k-1 variables, any locally consistent instantiation on LaTeX: Y is k-consistent.

For example, 3-consistency ensures that any instantiation any pair of variables can be extended to an instantiation involving any third variable without violating any constraint. It is equivalent to path consistency. Similarly, 2-consistency is also known as arc consistency.


Views
Personal tools