\begin{slide}{Hyperkantenkonsistenz}

  \begin{itemize}\itemsep 2pt
  \item 
Ein Atom $C(x_1,\ldots,x_n)$ 
mit Bereichszuordnung $\dom: x_i\mapsto D_i$
heißt $n$-(hyperkanten-)konsistent,

wenn $\forall p_i\in D_i \exists q_1\in D_1, \ldots, q_n\in D_n:
C(q_1,\ldots,q_{i-1},p_i,q_{i+1},\ldots,q_n)$.

Eine Formel ist $n$-konsistent, wenn alle Atome mit $\le n$ Variablen $n$-konsistent sind
\item
  Inferenzregel?
\item Aufwand? (Antwort: $O(|U|^n$)
\item Nutzen? (Antwort: Einsparung von Decide-Knoten)
\item beachte: Erweiterungen dieser Def. auf folgenden Folien
  \end{itemize}
\end{slide}

\begin{slide}{Hyperkantenkonsistenz und Konflikte}

durch Hyperkanten-Inferenz kann man Konflikte feststellen:

Bsp. $(x_1+x_2<x_3)$ mit $D_1=\{1,2\}, D_2=\{1,2\}, D_3=\{0,1\}$

\begin{verbatim}
Arc_Consistency_Deduction 
   { atom = x1 +x2 < x3 
   , variable = x3, restrict_to = [  ] 
   }
\end{verbatim}
es wird ein \emph{failed}-state erreicht ($\dom(x_3)=\emptyset$)

danach ist \verb|Backtrack| möglich.

(das ist die \emph{einzige} Möglichkeit der Konflikt-Feststellung
in autotool-Aufgabe)

\end{slide}

\begin{slide}{Hyperkantenkonsistenz: Erweiterungen}

Bsp. $(x_1+x_2<x_3)$ mit $D_1=\{0,1\}, D_2=\{0,1\}, D_3=\{1\}$
\begin{itemize}\itemsep 2pt
\item nach Definition: das ist trivial 2-konsistent (es gibt keine 2-Atome),
  aber nicht 3-konsistent
\item Erweiterung: da $x_3$ eindeutig ist: setze ein, 
  erhalte 2-Atom $(x_1+x_2<1)$, nicht 2-konsistent (betrachte $x_1=1$)
\end{itemize}

\bigskip

Bsp. $(x_1\le x_2  \wedge x_1\neq x_2)$ 
mit $D_1=\{0,1,2\},D_2=\{0,1,2\}$

\begin{itemize}\itemsep 2pt
\item nach Definition: das ist 2-konsistent (jedes 2-Atom wird dabei einzeln betrachtet)
\item Erweiterung: betrachte Konjunktion der Atome, dann nicht 2-konsistent,
(betrachte $x_1=2$)

\end{itemize}




\end{slide}
