système de réécriture

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).