On the DAC example in the class..

[Subbarao Kambhampati <rao@asu.edu>]

Folks

Here is the formal definition of DAC--

 A network is DAC relative to an order {x1...xn} iff every variable xi is arc-consistent relative to every

variable xj such that i < j. 

In other words,  given a variable V, we remove from it any value which won't allow the *future* variables

a feasible value. 

For the  example shown in class, the network will be DAC with order X--Y--Z,  if you have X with {1}, Y with just {1,2} and Z with {1,2,3}

The best way to enforce DAC is to start in the reverse order of the given direction. So we start from Z, realize that Y can't have 3 in its domain. Then go to Y, and realize that X can't have 2 or 3 in its domain.   

You will never retrace the direction. 

[I corrected the example in the slides now]]

Sorry for the confusion in the class.

Rao