Not logged in. · Lost password · Register

 Member since Oct 2014 18 posts 2019-02-06, 09: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 94 posts 2019-02-06, 11: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 806 posts 2019-02-06, 11:35   #3   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: Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys:
Special characters:
Go to forum
Datenschutz | Kontakt