\begin{slide}{Verarbeitung von XPATH-Ausdrücken}

XPATH-Ausdruck $R$ beschreibt Relation auf Knoten.

ausgehend von aktuellem Knoten $x$,
beschreibt Menge $R(x)=\{y \mid(x,y)\in R\}$.

für Implementierung:
\begin{itemize}
\item
  alle Elemente solcher Mengen effizient bestimmen
\item
  entscheiden, ob Menge leer ist
\end{itemize}



\end{slide}

\begin{slide}{Endliche Automaten}

wenn der Ausdruck $R$ nur Achsen-Schritte
und einfache Knotentests enthält,
dann kann man $R(x)$ durch endlichen Automaten darstellen.

\dots und damit die Fragen effizient beantworten.

(\emph{einfach}: Vergleich mit vorgegebenen Werten)
(nicht einfach: Rechnungen mit Zahlen usw.)
\bigskip

Wenn das zu transformierende Dokument groß ist,
lohnt sich die vorherige Berechnung solcher Hilfsmittel.

\bigskip

Beispiele: gegeben $w=[3,1,2]$.
und maximaler Knotengrad $3$.
Bestimme reguläre Ausdrücke für 
die Mengen $C^*(w), R(w)$.

\end{slide}



