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
Wichtige Eigenschaften sind Termination und Confluence. Termination bedeutet, dass jede Folge von Reduktionen endlich endet. Confluence
Beispiele und Verfahren: Ein einfaches String-Rewriting-System R = {AA -> A, AB -> BA} reduziert bestimmte Muster; es kann
Anwendungen: Rewriting-Systeme finden Verwendung in der automatischen Beweisführung, algebraischer Vereinfachung, Programmtransformation, Optimierung von Compilern und Symbolberechnungen.