This article has not yet been rated on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist
worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }
puts (x,y) and (y,x) in the worklist. However, suppose we have reduced the domain of x while checking (x,y), then later reduced the domain of y for the first time while checking (y,x) (hence, with the current implementation, the (x,y) arc is not put back in the worklist). Isn't it possible that this reduction of the domain of y implies a reduction of the domain of x ?
If so, you just need to change
worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) }
to
worklist := worklist + { (z, x) | there exists a relation R2(z, x) or a relation R2(z, x) }
If you're not sure either, that version works anyway.
Also, I'm wondering if directed constraints exist (a constraint R2(x,y) such that you need to check the domain of x if the domain of y has been reduced but not the opposite). If so, it would be better to change
worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }
to
worklist := { (x, y) | there exists a relation R2(x, y) }
Thanks for your time.
Baha2490 ( talk) 00:58, 6 March 2013 (UTC)
The text says that because of inefficiencies of early implementations and difficulties of modern implementations: "... and so AC-3 is the one most often taught ...". I don't understand this conclusion. I suspect this needs to be reworded? 91.2.85.9 ( talk) 18:22, 3 March 2016 (UTC)
This article has not yet been rated on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist
worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }
puts (x,y) and (y,x) in the worklist. However, suppose we have reduced the domain of x while checking (x,y), then later reduced the domain of y for the first time while checking (y,x) (hence, with the current implementation, the (x,y) arc is not put back in the worklist). Isn't it possible that this reduction of the domain of y implies a reduction of the domain of x ?
If so, you just need to change
worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) }
to
worklist := worklist + { (z, x) | there exists a relation R2(z, x) or a relation R2(z, x) }
If you're not sure either, that version works anyway.
Also, I'm wondering if directed constraints exist (a constraint R2(x,y) such that you need to check the domain of x if the domain of y has been reduced but not the opposite). If so, it would be better to change
worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }
to
worklist := { (x, y) | there exists a relation R2(x, y) }
Thanks for your time.
Baha2490 ( talk) 00:58, 6 March 2013 (UTC)
The text says that because of inefficiencies of early implementations and difficulties of modern implementations: "... and so AC-3 is the one most often taught ...". I don't understand this conclusion. I suspect this needs to be reworded? 91.2.85.9 ( talk) 18:22, 3 March 2016 (UTC)