Member since Oct 2014
18 posts

20190206, 08:29 #1
Subject: Arc consistency
Are two variables (u,v) arc consistent, if $C_{uv} \notin C$ and ($d_u = \emptyset$ or $d_v = \emptyset$)?

Member since Jul 2016
92 posts

20190206, 10:29 #2
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. 
Member since Oct 2016
803 posts

20190206, 10:35 #3
In reply to post #1
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 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 
Datenschutz 
Kontakt
Powered by the Unclassified NewsBoard software, 20150713dev,
© 20032011 by Yves Goergen