Ces dernières années, on a assisté au développement du<br />calcul de réécriture, encore appelé rho-calcul, qui intègre de<br />façon uniforme la réécriture de premier ordre et le lambda-calcul.<br />Cette thèse est dédiée à l'étude des capacités d'expression du calcul de réécriture, avec un intérêt particulier pour la réécriture d'ordre supérieur et la possibilité de manipuler des graphes.<br /><br />Dans la première partie de cette thèse, la relation entre le calcul de réécriture et la réécriture d'ordre supérieur, en particulier les Combinatory Reduction Systems (CRSs), est étudiée.<br />Nous présentons d'abord un algorithme de filtrage original<br />pour les CRSs qui utilise une traduction des termes CRS en<br />lambda-termes et le filtrage d'ordre supérieur classique du lambda-calcul. Nous proposons ensuite un encodage des CRSs dans le rho-calcul<br />basé sur la traduction de chaque réduction CRS<br />en une réduction correspondante dans le rho-calcul.<br />Dans la deuxième partie, nous présentons une extension du rho-calcul,<br />appelé calcul de réécriture de graphes (ou Rg-calcul),<br />qui gère des termes avec partage et cycles.<br />Le calcul sur les termes est généralisé de manière naturelle en utilisant des contraintes d'unification en plus des contraintes de filtrage standard du rho-calcul.<br /><br />Le Rg-calcul est alors montré confluent sur des classes<br />d'équivalence de termes, sous certaines restrictions de linéarité sur les motifs, et assez<br />expressif pour simuler la réécriture de termes graphes et le<br />lambda-calcul cyclique.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00011037 |
| Date | 28 October 2005 |
| Creators | Bertolissi, Clara |
| Publisher | Institut National Polytechnique de Lorraine - INPL |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0018 seconds