Termersetzungssystem

Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik. Sie bilden insbesondere die Grundlage der Logik- und funktionalen Programmierung. Ferner spielen sie eine wichtige Rolle beim Wortproblem und bei der Terminierungsanalyse.

Termersetzungssysteme sind Mengen von Termersetzungsregeln. Diese Mengen kann man sich wie Gleichungssysteme zwischen Termen vorstellen, bei dem die Gleichungen nur von links nach rechts angewendet werden dürfen.

Beispiel

   plus(0, y)  →  y
   plus(succ(x), y)  →   succ(plus(x, y))

Die oben stehenden Regeln bilden ein Termersetzungssystem, welches als die Addition zweier natürlicher Zahlen verstanden werden kann. Dies erfordert, dass man die Zahl 0 mit dem Term 0, die Zahl 1 mit dem Term succ(0), die Zahl 2 mit dem Term succ(succ(0)) usw. repräsentiert. Die Regeln besagen, dass beispielsweise jedes Vorkommen von ${\displaystyle \operatorname {plus} (0,y)}$ in einem Term durch ${\displaystyle y}$ ersetzt werden darf. Dabei kann ${\displaystyle y}$ selbst ein beliebiger Term sein, muss also insbesondere auch keine natürliche Zahl darstellen.

Termersetzungssysteme sind turingvollständig, stehen also, was die Berechnungsstärke angeht, anderen Formalismen wie den Turingmaschinen, dem Lambda-Kalkül oder Registermaschinen in nichts nach. Da sie vergleichsweise einfach strukturiert sind und von Computern gut gehandhabt werden können, stellen die Termersetzungssysteme ein wichtiges Hilfsmittel in der computergestützten Analyse von Algorithmen dar.

Definitionen

Um ein Termersetzungssystem aufzubauen, benötigt man zunächst eine klare Vorstellung von den zu Grunde liegenden Begriffen.

Terme

Für eine Menge ${\displaystyle \Sigma }$ von Funktionssymbolen und eine (unendliche) Menge ${\displaystyle {\mathcal {V}}}$ von Variablen definiert man die Menge ${\displaystyle {\mathcal {T}}(\Sigma ,{\mathcal {V}})}$ der Terme induktiv wie folgt:

• Jede Variable und jedes nullstellige Funktionssymbol (d. h. jede Konstante) ist ein Term.
• Sind ${\displaystyle t_{1},\dots ,t_{n}}$ Terme und ist ${\displaystyle f}$ ein n-stelliges Funktionssymbol, so ist ${\displaystyle f(t_{1},\dots ,t_{n})}$ ebenfalls ein Term.

Man bemerke, dass diese Definition genau der Definition eines mathematischen Termes entspricht.

Ohne formale Definition seien noch folgende Begriffe erwähnt:

• Eine Substitution ordnet einigen Variablen neue Terme zu. Eine Substitution wirkt auf einen Term, indem jedes Vorkommen einer Variable durch den von der Substitution vorgegebenen Term ersetzt wird. Lautet die Substitution beispielsweise ${\displaystyle \sigma =\{x/f(x,y)\}}$ und ist ${\displaystyle t=g(x)}$ ein Term, so ist ${\displaystyle t\sigma =g(f(x,y))}$ der Term, der durch Anwenden von ${\displaystyle \sigma }$ auf ${\displaystyle t}$ entsteht.
• Ein Term ${\displaystyle t}$ matcht einen Term ${\displaystyle s}$, wenn es eine Substitution ${\displaystyle \sigma }$ gibt, so dass ${\displaystyle t\sigma =s}$ gilt. Beispielsweise matcht ${\displaystyle g(x)}$ den Term ${\displaystyle g(f(x,y))}$.

Termersetzungsregeln

Eine Termersetzungsregel ist ein Paar ${\displaystyle l\rightarrow r}$ zweier Terme ${\displaystyle l,r}$, wobei ${\displaystyle l}$ keine Variable sein darf und ferner in ${\displaystyle r}$ keine Variable vorkommen darf, die nicht auch in ${\displaystyle l}$ vorkommt. Der Grund dieser Einschränkung hängt mit der Terminierung eines Termersetzungssystems zusammen und wird im entsprechenden Abschnitt näher erläutert.

Die Termersetzungsrelation

Die „Funktionsweise“ eines Termersetzungssystems wird über die Termersetzungsrelation ${\displaystyle \rightarrow _{\mathcal {R}}}$ definiert.

Anschauliche Beschreibung

Passt auf einen Term ${\displaystyle s}$ oder einen Teilterm von ${\displaystyle s}$ die linke Seite einer Regel, so kann man diese linke Seite in ${\displaystyle s}$ durch die rechte Seite der entsprechenden Regel ersetzen und so einen neuen Term ${\displaystyle t}$ erhalten. Dies soll an einigen Beispielen gezeigt werden. Dazu betrachten wir das einfache Termersetzungssystem

   f(x,y) → x

• Den Term ${\displaystyle f(s(y),g(x))}$ kann man mit dieser Regel zu ${\displaystyle s(y)}$ auswerten.
• ${\displaystyle g(f(a,b))}$ kann man zu ${\displaystyle g(a)}$ auswerten.
• ${\displaystyle f(f(a,b),c)}$ kann man in einem Schritt sowohl zu ${\displaystyle f(a,c)}$ als auch zu ${\displaystyle f(a,b)}$ auswerten.

Formale Definition

Ein Term ${\displaystyle s}$ wertet zu ${\displaystyle t}$ aus, geschrieben ${\displaystyle s\rightarrow _{\mathcal {R}}t}$, falls folgendes gilt:

• Es gibt eine Substitution ${\displaystyle \sigma }$ und
• eine Regel ${\displaystyle l\rightarrow _{\mathcal {R}}r}$ in ${\displaystyle {\mathcal {R}}}$, so dass
• ${\displaystyle s}$ den Term ${\displaystyle l\sigma }$ enthält und
• ${\displaystyle t}$ an derselben Stelle den Term ${\displaystyle r\sigma }$ enthält, ansonsten aber mit ${\displaystyle s}$ übereinstimmt.

Fragestellungen

Je nach Anwendungsbereich eines Termersetzungssystems gibt es mehrere Fragestellungen, welche von Interesse sind. Dies sind unter anderem:

Terminierung

Hierbei stellt man sich die Frage, ob es zu einem Termersetzungssystem ${\displaystyle {\mathcal {R}}}$ Terme gibt, die eine unendliche Kette von Auswertungen ${\displaystyle s\rightarrow _{\mathcal {R}}s_{1}\rightarrow _{\mathcal {R}}s_{2}\rightarrow _{\mathcal {R}}\dots }$ erlauben, oder ob alle Ableitungen aller Terme stets endlich sind. Ist letzteres der Fall, nennt man ${\displaystyle {\mathcal {R}}}$ auch terminierend oder fundiert.

Zwar ist die Frage nach der Terminierung in jedem turingvollständigen Berechnungssystem unentscheidbar. Jedoch existiert eine Menge fortgeschrittener Techniken, um die Terminierung vieler Termersetzungssysteme automatisch nachzuweisen. Ein allgemeiner Ansatz ist, eine fundierte Ordnung ${\displaystyle \succ }$ mit ${\displaystyle {\rightarrow _{\mathcal {R}}}\subseteq {\succ }}$ zu finden, so dass ${\displaystyle l\succ r}$ für alle Regeln ${\displaystyle l\rightarrow _{\mathcal {R}}r}$ des TES gilt. Außerdem muss diese Ordnung erhalten bleiben, wenn man Substitutionen auf ${\displaystyle l}$ und ${\displaystyle r}$ anwendet (die Ordnung muss stabil sein) oder wenn ${\displaystyle l}$ und ${\displaystyle r}$ als Teilterme eines anderen Terms auftreten (die Ordnung muss monoton sein). Es existieren noch zahlreiche andere Methoden. Man kann die Terme beispielsweise als Polynome oder Matrizen interpretieren sowie eine genauere Analyse der Abhängigkeiten der Funktionssymbole untereinander durchführen. Hierfür sei auf die weiterführende Literatur verwiesen.

Konfluenz

Ausgehend von einem Term kann es mehrere mögliche Ableitungen geben. Mit Konfluenz bezeichnet man die Eigenschaft eines Termersetzungssystems, dass zwei Terme, die in mehreren Schritten auf unterschiedliche Art aus einem Ausgangsterm hervorgehen, stets wieder zu einem Term zusammengeführt werden können. Eine damit zusammenhängende Frage ist, ob die durch ein Termersetzungssystem beschriebene Berechnung für dieselbe Eingabe stets zu demselben Ergebnis (eindeutige Normalform) kommt. Konfluenz ist im Allgemeinen ebenso unentscheidbar wie die Terminierung.

Ein Termersetzungssystem, das terminiert und konfluent ist, bezeichnet man auch als konvergent. Für solche Systeme existiert zu jedem Term eine eindeutige Normalform. Es ist entscheidbar, ob ein terminierendes Termersetzungssystem konfluent ist.^[1]

Anwendungen

Als mathematisch relativ leicht handhabbares Konstrukt eignen sich Termersetzungssysteme für die computergestützte Behandlung von Problemen aus der theoretischen Informatik. Einige Anwendungen sind:

Entscheidungsverfahren für das Wortproblem

Ein Termgleichungssystem ${\displaystyle {\mathcal {E}}}$ ist eine Menge von Gleichungen zwischen Termen. Unter dem Wortproblem für ${\displaystyle {\mathcal {E}}}$ versteht man die Frage, ob eine Gleichung ${\displaystyle s=t}$ gilt unter der Voraussetzung, dass die Gleichungen in ${\displaystyle {\mathcal {E}}}$ wahr sind. Als Beispiel könnte man in ${\displaystyle {\mathcal {E}}}$ die Gruppenaxiome kodieren:

   f(x, f(y,z))  =  f(f(x,y), z)
   f(x, e)       =  x
   f(x, i(x))    =  e

Hierbei steht das zweistellige Funktionssymbol ${\displaystyle f}$ für die Gruppenverknüpfung, die einstellige Funktion ${\displaystyle i}$ liefert die inversen Elemente, und die Konstante ${\displaystyle e}$ bezeichnet das neutrale Element; ${\displaystyle x}$, ${\displaystyle y}$ und ${\displaystyle z}$ sind Variablen. Man sucht nun nach einem Verfahren, automatisch Gleichungen wie ${\displaystyle i(e)=e}$ oder ${\displaystyle i(i(x))=x}$ auf ihren Wahrheitsgehalt hin zu überprüfen.

Zu diesem Zweck konstruiert man zum Gleichungssystem ${\displaystyle {\mathcal {E}}}$ ein äquivalentes und konvergentes Termersetzungssystem ${\displaystyle {\mathcal {R}}}$. Äquivalent bedeutet hier, dass ${\displaystyle s=t}$ gilt genau dann wenn ${\displaystyle s\leftrightarrow _{\mathcal {R}}^{*}t}$. Die Schreibweise ${\displaystyle \leftrightarrow _{\mathcal {R}}^{*}}$ bedeutet, dass die Termersetzungsrelation hier beliebig oft und in beiden Richtungen angewendet werden kann.

Hat man nun ein solches konvergentes TES gegeben, lässt sich das Wortproblem ${\displaystyle s=t}$ lösen, indem man einfach ${\displaystyle s}$ und ${\displaystyle t}$ mittels ${\displaystyle \rightarrow _{\mathcal {R}}}$ solange auf beliebige Weise auswertet, bis keine weitere Auswertung mehr möglich ist. Da das TES nach Voraussetzung konvergent ist, gibt es keine unendliche Auswertung. Das Verfahren selbst terminiert also. Da das TES außerdem konfluent ist, spielt es keine Rolle, welche der möglichen Auswertungen man wählt. Führt nun die Auswertung der beiden Terme zu ein und demselben Term, so gilt ${\displaystyle s=t}$ für die Gleichungen von ${\displaystyle {\mathcal {E}}}$.

Da das Wortproblem unentscheidbar ist, lässt sich nicht immer ein konvergentes Termersetzungssystem finden, das das Wortproblem für das entsprechende Gleichungssystem entscheidbar macht. Ein Verfahren zu Konstruktion von konvergenten Termersetzungssystemen ist das Knuth-Bendix Vervollständigungsverfahren.^[1] Es berechnet im Erfolgsfall zu einer gegebenen Gleichungsmenge und einer fundierten Termordnung ein äquivalentes und konvergentes Termersetzungssystem. Allerdings ist weder die Termination noch der Erfolg des Knuth-Bendix Vervollständigungsverfahrens garantiert. Für den Fall der Gruppenaxiome oben berechnet das Knuth-Bendix Vervollständigungsverfahren z. B. das folgende konvergente Termersetzungssystem:

   f(x, e)          ->  x
   f(e, x)          ->  x
   f(x, i(x))       ->  e
   f(i(x), x)       ->  e
   f(f(x,y), z)     ->  f(x, f(y,z))
   f(x, f(i(x),y))  ->  y
   f(i(x), f(x,y))  ->  y
   i(e)             ->  e
   i(i(x))          ->  x
   i(f(x, y))       ->  f(i(y), i(x))

Terminierungsanalyse

Da für Termersetzungssysteme so viele mächtige Techniken existieren, welche die Terminierung nachweisen können, transformiert man Programme höherer Programmiersprachen in Termersetzungssysteme und wendet diese Techniken darauf an. Das Tool AProvE, welches an der RWTH Aachen entwickelt wird, hat dies bisher für die Programmiersprachen Prolog und Haskell implementiert.

Die Behandlung imperativer und objektorientierter Sprachen, wie beispielsweise Java, ist Gegenstand aktueller Forschung.

Literatur

• F. Baader, T. Nipkow: Term Rewriting and All That. Cambridge University Press, 1999.
• J. Avenhaus: Reduktionssysteme. Springer-Verlag, 1995, ISBN 3-540-58559-1.
• R. Bündgen: Termersetzungssysteme Theorie, Implementierung, Anwendung. Vieweg 1998, ISBN 3-528-05652-5; PostScript, PDF
• TeReSe. Term Rewriting Systems. Cambridge University Press, 2003, ISBN 0-521-39115-6

Weblinks

• IFIP Working Group 1.6
• Tool, welches unter anderem die Terminierung von Termersetzungssystemen sowie Prolog- und Haskell-Programmen automatisch beweisen kann.
• Portalseite der Terminationscommunity

Einzelnachweise

1. D. E. Knuth, P. B. Bendix: Simple word problems in universal algebra. In: Computational Problems in Abstract Algebra. Pergamon Press, 1970.