Not logged in. · Lost password · Register

Nora Go
Member since Oct 2014
18 posts
Subject: Arc consistency
Are two variables (u,v) arc consistent, if $C_{uv} \notin C$ and ($d_u = \emptyset$ or $d_v = \emptyset$)?
Jonas S
Member since Jul 2016
92 posts
Yes, but only because the first condition C_{uv} \notin C is already sufficient. The second conjunct is not sufficient,
because d_v = \emptyset does not guarantee arc consistency.d_u = \emptyset is sufficient, since quantifying over an empty set is always true. Also note that d_v = emptyset conditions aren't really relevant for arc consistency, because any algorithm should detect empty domains.
Jazzpirate
Member since Oct 2016
803 posts
In reply to post #1
Are two variables (u,v) arc consistent
OBJECTION. Arc consistency is not symmetric - u can be arc consistent relative to v, v can be arc consistent relative to u, or both, or neither. Just to be clear ;)

if $C_{uv} \notin C$ and ($d_u = \emptyset$ or $d_v = \emptyset$)?
So the definition of u being arc consistent relative to v is that "For all x\in d_u, there exists some y \in d_v such that...". A statement of the form "for all x\in S" is always true if S is the empty set. So if d_u is empty, then u is arc consistent relative to every other variable.
A statement of the form "there exists some x\in S..." is always false if S is the empty set. So if d_u is *not* empty, but d_v is, then u is *not* arc consistent relative to v.

Now, if neither d_u nor d_v are empty, but C_{uv} not in C, then there is no constraint between u and v, so so any pair of values from d_u and d_v is (in principle, barring other constraints) valid, so u is arc consistent relative to v and v is arc consistent relative to u :)
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen