1.1 --- a/exercises/solutions/sol04.tex	Thu May 31 04:12:51 2012 +0200
     1.2 +++ b/exercises/solutions/sol04.tex	Thu May 31 17:36:51 2012 +0200
     1.3 @@ -149,9 +149,9 @@
     1.4  \end{tikzpicture}
     1.5  \caption{(3.1b) primal constraint graph of $N$}
     1.6  \end{figure}\\
     1.7 -(c) No, $N$ is not arc-consistent. We provide the arc-consistent constraint network $N^c=\langle V, D^c, C\rangle$ with
     1.8 +(c) No, $N$ is not arc-consistent. We provide the arc-consistent constraint network $N'=\langle V, D', C\rangle$ with
     1.9  \begin{align*}
    1.10 -  D^c_{v}=\left\{
    1.11 +  D'_{v}=\left\{
    1.12      \begin{array}{l l}
    1.13        \{1\} & v = norwegian\\
    1.14        \{3\} & v = milk\\
    1.15 @@ -174,6 +174,17 @@
    1.16  
    1.17  Let $\C=\langle V,D,C\rangle$ and $\C'=\langle V,D',C\rangle$. By definition each variable assignment $a(v_i)$ must be in its variable domain $D_i$, i.e., $a(v_i)\in D_i$. Therefore, a reduction of domains can only yield a network with less solutions. Since AC3 reduces domains, there can not be more solutions for $\C'$, i.e., $Sol(\C') \subseteq Sol(\C)$.
    1.18  
    1.19 -Assume that solution $a\in Sol(\C)$ is lost after the domain reduction by AC3, i.e., $a\notin Sol(\C')$. WLOG it follows that at some iteration of AC3 the value $a(v_i)$ was removed from the domain $D_i'$, so it holds $a(v_i)\notin D_i'$. By the definition of the revise function of AC3, it holds that $D_i'\leftarrow D_i\cap\pi_i(R_{ij} \bowtie D_j)$. Since $a(v_i)$ is in $D_i$ but not in $D_i'$, it follows that $a(v_i)\notin\pi_i(R_{ij}\bowtie D_j) \implies (a(v_i),a(v_j))\notin(R_{ij}\bowtie D_j)$. The join $R_{ij}\bowtie D_j$ represents the set of all consistent assignments of variable $v_j$ over the relation $R_{ij}$. With $(a(v_i),a(v_j))\notin (R_{ij}\bowtie D_j)$ it follows that variable assignments $(a(v_i),a(v_j))$ are not consistent with the constraint over $R_{ij}$. It contradicts with our assumption that $a\in Sol(\C)$, because a solution must satisfy all constraints of the network. We have shown that there is no solution $a\in Sol(\C)$, such that $a\notin Sol(\C')$. \qed\\\\
    1.20 -(b) 
    1.21 +Assume that solution $a\in Sol(\C)$ is lost after the domain reduction by AC3, i.e., $a\notin Sol(\C')$. WLOG it follows that at some iteration of AC3 the value $a(v_i)$ was removed from the domain $D_i'$, so it holds $a(v_i)\notin D_i'$. By the definition of the revise function of AC3, it holds that $D_i'\leftarrow D_i\cap\pi_i(R_{ij} \bowtie D_j)$. Since $a(v_i)$ is in $D_i$ but not in $D_i'$, it follows that $a(v_i)\notin\pi_i(R_{ij}\bowtie D_j) \implies (a(v_i),a(v_j))\notin(R_{ij}\bowtie D_j)$.
    1.22 +
    1.23 +The join $R_{ij}\bowtie D_j$ represents the set of all consistent assignments of variable $v_j$ over the relation $R_{ij}$. With $(a(v_i),a(v_j))\notin (R_{ij}\bowtie D_j)$ it follows that variable assignments $(a(v_i),a(v_j))$ are not consistent with the constraint over $R_{ij}$. It contradicts with our assumption that $a\in Sol(\C)$, because a solution must satisfy all constraints of the network. We have shown that there is no solution $a\in Sol(\C)$, such that $a\notin Sol(\C')$. \qed\\\\
    1.24 +%
    1.25 +(b) To show that AC3 produces an arc-consistent network $\C'$ we consider three cases. The first case is trivial, given an arc-consistent network the revise function does not remove any domain values and therefore does not modify the network.
    1.26 +
    1.27 +Let $\C$ be a network with some not arc-consistent $R_{ij}$, i.e., there is some assignment a with $a(v_i)\in D_i$, $a(v_j)\in D_j$ and $(a(v_i),a(v_j))\notin (R_{ij}\bowtie D_j)$. Initially, AC3 does revise all variable pairs $(v_i,v_j)$ and $(v_j,v_i)$ with $(v_i,v_j)$ in some constraint's scope ($R_{ij}$). It follows that AC3 does revise $(v_i,v_j)$ in respect of $R_{ij}$ in some iteration and reduces $D_i'\leftarrow D_i\cap\pi_i(R_{ij}\bowtie D_j)$. Because $(a(v_i),a(v_j))\notin (R_{ij}\bowtie D_j)$ implies $a(v_i)\notin\pi_i(R_{ij}\bowtie D_j)$, it holds that $a(v_i)\notin D_i'$. This reduces the initial arc-inconsitency of $v_i$ relative to $v_j$.
    1.28 +
    1.29 +By the domain value reduction, AC3 can introduce new not arc-consistent constraints. Let $a(v_i)\in D_i$ be a value, that was removed by the revise function for constraint $R_{ij}$. Since the revise function changed $D_i$, AC3 will again revise all variable pairs $(v_k,v_i)$ with $k\neq i,k\neq j$ for all constraints $R_{ki}$. This removes all inconsistent values for all domains $D_k$,i.e., all $a(v_k)\in D_k$ with $a(v_k)\notin\pi_k(R_{ki}\bowtie D_i)$ are removed from $D_k$. All other constraints $R_{lm}$ with $m\neq i$ are not directly affected by the reduced domain $D_i$ and can therefore not become not arc-consistent by the revisal of $(v_i,v_j)$. 
    1.30 +
    1.31 +We have shown, that all initial not arc-consistent constraints are made arc-consistent and the same holds for all newly introduced inconsistencies by the domain reduction. It follows that all remaining domains of $\C'$ form an arc-consistent network. \qed\\\\
    1.32 +%
    1.33 +(c)
    1.34  \end{document}