Skip to Main content Skip to Navigation
Theses

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 metadatas

Cited literature [122 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/tel-01752520
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 1:50:11 PM
Last modification on : Tuesday, April 24, 2018 - 1:30:10 PM

File

2005_BERTOLISSI_C.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01752520, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

70

Files downloads

48