RewritingSystemen

RewritingSystemen bezeichnet in der theoretischen Informatik formale Modelle der Berechnung, bei denen Ausdrücke durch wiederholte Anwendung von Ersetzungsregeln umgeschrieben werden. Ziel ist es, einen Ausdruck in eine normale Form zu überführen, unabhängig von der Reihenfolge der Regelanwendung. Man unterscheidet vor allem zwei Varianten: String-Rewriting, bei dem es um Wörter über einem Alphabet geht, und Term-Rewriting, bei dem algebraische Terme mit Funktionssymbolen und Variablen bearbeitet werden.

Bei String-Rewriting besteht der Reduktionsschritt darin, eine Teilzeichenkette l durch eine Zeichenkette r gemäß der Regel l → r zu ersetzen. Bei Term-Rewriting besteht eine Regel aus einer linken Seite l und einer rechten Seite r, wobei l eine Nicht-Variable ist und Variablen in l in r erscheinen dürfen. Die Reduktion wird durch eine Relation -> auf Ausdrücken bzw. Termen definiert.

Wichtige Eigenschaften sind Termination und Confluence. Termination bedeutet, dass jede Folge von Reduktionen endlich endet. Confluence bedeutet, dass verschiedene Reduktionspfade vom gleichen Ausgangsausdruck zur gleichen normalen Form führen. Ist beides gegeben, besitzt jeder Ausdruck eine eindeutige Normalform. Die Prüfung erfolgt oft durch Analyse kritischer Paare, Überschneidungen von linken Seiten der Regeln.

Beispiele und Verfahren: Ein einfaches String-Rewriting-System R = {AA -> A, AB -> BA} reduziert bestimmte Muster; es kann Terminierung besitzen, muss aber nicht zwangsläufig konvergieren. Zur Erreichung von Confluence werden oft heuristische Verfahren wie die Knuth-Bendix-Vervollständigung eingesetzt, um ein konfluentes System zu erzeugen, falls möglich.

Anwendungen: Rewriting-Systeme finden Verwendung in der automatischen Beweisführung, algebraischer Vereinfachung, Programmtransformation, Optimierung von Compilern und Symbolberechnungen. Sie dienen auch zur Formalisierung semantischer Umformungen in Programmiersprachen, zur Spezifikation von Rewrites und zur Modellierung von Rewrites in der theoretischen Forschung.