\begin{slide}{Achsen als Relationen}

Die Achsen beschreiben Relationen auf Positionen.

Wiederholung zu Relationen (ich hoffe jedenfalls):

\begin{itemize}\itemsep 7pt
\item
  eine \emph{Relation} $R$ über Menge $M$
  ist Menge von geordneten Paaren. $R \subseteq M\times M$.
\item das \emph{Produkt} von zwei Relationen $R, S$ ist
  $R\circ S = \{(x,z) 
  \mid \exists y: (x,y)\in R\wedge (y,z)\in S\}$
\item
  die \emph{transitive Hülle} von $R$ ist
  $R^+ = R^1 \cup R^2 \cup \ldots$.
\item
  die \emph{reflexive und transitive Hülle} von $R$ ist
  $R^ = R^0 \cup R^1 \cup R^2 \cup \ldots$,

  dabei ist $R^0$ die identische Relation $\{(x,x)\mid x\in M\}$
\item
  die inverse Relation von $R$ ist
  $R^- = \{ (y,x) \mid (x,y) \in R \}$
\end{itemize}
\end{slide}

\begin{slide}{Achsen als Relationen}

bezeichne mit $C$ die child-relation.
Das ist die Relation auf $\NN^*$ ($=$ Positionen)

$C = \{ (w, wx) \mid w \in \NN^*, x\in \NN \}$

Beispiel $([1,4,0],[1,4,0,3]) \in C$.

\begin{itemize}

\item descendant $= C^+$
\item descendant-or-self $=C^*$
\item parent $P = C^-$
\item ancestor $= P^+=(C^-)^+$ 
\item ancestor-or-self $= P^*= (C^-)^*$
\end{itemize}

\end{slide}

\begin{slide}{Achsen als Relationen (II)}

Die Relation following-sibling ist:

$r = \{ ( wx, wy ) \mid w\in\NN^*, x\in \NN, y\in\NN, x < y \}$.

Beispiel: $([2,5,1],[2,5,3]) \in r$.

($r$ wegen \emph{rechts}, 
alle weiter rechts stehenden 
Kinder des gleichen Elters)

\begin{itemize}
\item
  preceding-sibling $= l = r^-$
\end{itemize}

\end{slide}

\begin{slide}{Achsen als Relationen (III)}

was ist \emph{following} $(R)$ ? 
(großes $R$, wegen $r\subseteq R$)

Definition: alle Knoten, die \emph{nach} 
dem End-Tag des Kontextknotens \emph{beginnen}

\( R  = (C^-)^* \circ r \circ C^* \)

das ergibt vollständige Fallunterscheidung:
für beliebige Knoten (Positionen) $x,y$ 
gilt genau eines von:

\( 
x=y, 
(x,y)\in C^+, (x,y)\in (C^-)^+, 
(x,y)\in R, (x,y)\in R^- 
\)

\end{slide}

\begin{slide}{Kontrollfragen zu Achsen}

\begin{itemize}
\item
  sind diese Relationen gleich: $r \circ R$ und $R \circ r$?
\item
  wo liegen die Knoten $x$ mit der Eigenschaft $R(x)=\emptyset$?

  dabei bedeutet $R(x) = \{ y \mid (x,y)\in R\}$.
\end{itemize}

\end{slide}
