\begin{slide}{Prüfung von Transformationen}

Wenn für die Transformation auch 
die XML-Schema für Eingabe und Ausgabe bekannt sind,

dann kann (sollte) man   prüfen, 
ob jedes Resultat einer Transformation
tatsächlich ein Dokument erzeugt,  das zum Ausgabescheme paßt

\dots am liebsten automatisch.

Die Schemas beschreiben reguläre Baumsprachen,
die Transformation ist ein Term-Ersetzungs-System,
also ist das die Frage:

für welche Ersetzungssysteme $R$ gilt:
wenn $L$ eine reguläre Baumsprache,
dann ist auch $R^*(L)$ regulär
und kann effektiv bestimmt werden?

\end{slide}

\begin{slide}{Regularitäts-Erhaltung}

im Allgemeinen sind Ersetzungssysteme nicht REG-erhaltend,
aber in Spezialfällen (besondere Form der Regeln) doch.

\bigskip

\dots ist aktuelles Forschungsgebiet
innerhalb der Termersetzung,
z. B. auf Konferenzen RTA
(Rewriting Techniques and Applications).

\bigskip

Beispiele (Wortersetzung): alle linken Seiten Länge $=1$
oder alle rechten Seiten Länge $\le 1$
(aber nicht beides gleichzeitig!)


\bigskip

Beispiel
Für $S=\{100 \to 011, 001 \to 110\}$ (Solitär-Spiel)
bestimme $L = S^*(0^* 1 0^*)$ (abräumbare Anordnungen).

Diese Menge ist eine reguläre Sprache.

\end{slide}
