Regularitäts-Erhaltung

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

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

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

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

Diese Menge ist eine reguläre Sprache.