\begin{slide}{Kantenkonsistenz (Definition)}

  \begin{itemize}
  \item 
Eine Bereichszuordnung $\dom$ 

für ein binäres atomares Constraint $C(x,y)$ 

heißt \emph{kantenkonsistent} (arc-consistent), wenn gilt:

$\forall p\in \dom(x)\exists q\in\dom(y): C(p,q)$

und $\forall q\in \dom(y)\exists p\in\dom(x): C(p,q)$
\item
  Eine Bereichszuordnung $\dom$ für ein FD-Constraint $F$
  heißt kantenkonsistent, 
  wenn $\dom$ für jedes binäre Atom in $F$ kantenkonsistent ist.
  
  \end{itemize}

Beispiele, Zusammenhang zw. Kantenkonsistenz und globaler Konsistenz?
\end{slide}

\newcommand{\Arc}{\operatorname{Arc}}

\begin{slide}{Kantenkonsistenz (Herstellung)}

  \begin{itemize}
  \item 
für ein binäres Constraint $C(x,y)$ 

und Bereichszuordnung
$\dom(x)=P, \dom(y)=Q$:

\item
definiere die \emph{Projektionen}

$P' = \{ p \mid \exists q\in Q: C(p,q) \}$, \quad
$Q' = \{ q \mid \exists p\in P: C(p,q) \}$.

\item
und Inferenzregeln $\Arc_1: (P,Q)\mapsto(P',Q), \quad
\Arc_2: (P,Q)\mapsto (P, Q')$.

\item Satz: eine Zuordnung ist kantenkonsistent, 
wenn sie unter $\Arc_1$ und $\Arc_2$ abgeschlossen ist

\item Algorithmus: 
solange $\dom$ nicht kantenkonsistent ist,
wende $\Arc_1$ und $\Arc_2$ in beliebiger Reihenfolge an.



  \end{itemize}


\end{slide}
