Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Le calcul de réécriture de graphes : propriétés et capacités d'expression

Abstract : The last few years have seen the development of the rewriting calculus (also called rho-calculus) that uniformly integrates first-order term rewriting and lambda-calculus. This thesis is devoted to the study of the expressiveness of the rewriting calculus, with special interest for higher-order rewriting and the possibility of dealing with graph-like structures. The first part of the thesis is dedicated to the relationship between the rewriting calculus and higher-order term rewriting, namely the Combinatory Reduction Systems (CRSs). First, an original matching algorithm for CRSs terms that uses a simple term translation and the classical higher-order pattern matching of lambda terms is proposed and then an encoding of CRSs in the rho-calculus based on a translation of each possible CRS-reduction into a corresponding rho-reduction is presented. The second part of the thesis is devoted to an extension of the rho-calculus, called graph rewriting calculus (or Rg-calculus), handling terms with sharing and cycles. The calculus over terms is naturally generalised by using unification constraints in addition to standard rho-calculus matching constraints. The Rg-calculus is shown to be confluent over equivalence classes of terms, under some linearity restrictions on patterns, and expressive enough to simulate first-order term graph rewriting and cyclic lambda-calculus
Complete list of metadata

Cited literature [122 references]  Display  Hide  Download
Contributor : Thèses UL Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 1:50:11 PM
Last modification on : Saturday, October 16, 2021 - 11:26:09 AM


Files produced by the author(s)


  • HAL Id : tel-01752520, version 1



Clara Bertolissi. Le calcul de réécriture de graphes : propriétés et capacités d'expression. Autre. Institut National Polytechnique de Lorraine, 2005. Français. ⟨NNT : 2005INPL085N⟩. ⟨tel-01752520⟩



Record views


Files downloads