rewriting

In mathematics, computer science, and logic, rewriting covers a wide range of (potentially non-deterministic) methods of replacing subterms of a formula with other terms. What is considered are rewriting systems (also known as rewrite systems, rewrite engines or reduction systems). In their most basic form, they consist of a set of objects, plus relations on how to transform those objects.

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.

La réécriture (ou récriture) est un modèle de calcul utilisé en informatique, en algèbre, en logique mathématique et en linguistique. Il s’agit de transformer des objets syntaxiques (mots, termes, lambda-termes, programmes, preuves, graphes…) en appliquant des règles bien précises. Voici quelques exemples classiques d’utilisation de la réécriture :

• simplifier une expression algébrique (calcul formel) ;
• définir la grammaire formelle d’un langage de programmation ou d’une langue naturelle (analyse syntaxique) ;
• exprimer la sémantique d’un langage de programmation (sémantique opérationnelle) ;
• étudier la structure d’un groupe ou d’un monoïde (combinatoire algébrique) ;
• expliciter le contenu calculatoire d’une démonstration mathématique par le mécanisme d’élimination des coupures (théorie de la démonstration).