Menge von (meist strukturierten) Objekten, versehen mit einer Menge von Ersetzungsregeln.

Eine Ersetzungsregel ist ein Paar von Teilobjekten.

Bei Vorfinden der linken Seite einer Ersetzungsregel als Teil eines Objektes kann dieses Teil gegen die rechte Seite der Regel eingetauscht werden. Ersetzungsregeln sind üblicherweise parametrisiert, sodaß vor Regelanwendung eine geeignete Parameterzuordnung gewühlt werden muß. Ersetzungsregeln können als Gleichungen über dem gegebenen Objektbereich angesehen werden, die grundsätzlich von links nach rechts anzuwenden sind. Rewriting-Systeme gestatten also symbolisches Rechnen auf dem entsprechenden Objektbereich.

Die Gleichungssicht auf Ersetzungsregeln definiert eine Äquivalenzrelation auf den Objekten. Zur algorithmischen Verifikation dieser Äquivalenz versucht man, den einzelnen Objekten Normalformen zuzuordnen. Dies sind Objekte, die aus dem gegebenen Objekt durch (mehrfache) Ersetzungen entstehen, und auf die keine weiteren Regeln anwendbar sind. Um die Existenz und Eindeutigkeit von Normalformen zu sichern, fordert man von Rewriting-Systemen Eigenschaften wie Terminierung (es gibt keine unendlichen Ketten von Ersetzungen) und Konfluenz (eine gewisse Unabhängigkeit des Ergebnisses mehrerer Regelanwendungen von der Anwendungsreihenfolge).

Rewriting-Systeme gibt es für viele Strukturen, darunter sind Wortersetzungssysteme, Termersetzungssysteme und Graphersetzungssysteme. Sie werden u. a. bei der Sprachverarbeitung, in Computeralgebrasystemen und zum Theorembeweisen eingesetzt. Außerdem werden sie zur semantischen Fundierung verschiedener syntaktischer Kalküle herangezogen.