Term-graph rewriting via explicit paths - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2007

Term-graph rewriting via explicit paths

Résumé

The notion of path is classical in graph theory but not directly used in the term rewriting community. The main idea of this work is to raise the notion of path to the level of first-order terms, i.e. paths become part of the terms and not just meta-information about them. These paths are represented by sequences of integers (positive or negative) and are interpreted as relative addresses in terms. In this way, paths can also be seen as a generalization of the classical notion of position for the first-order terms and of de Bruijn indexes for the lambda calculus. In this paper, we define an original framework called Addressed Term Rewriting where paths are used to represent pointers between subterms. Using this approach, any term-graph rewriting systems can be efficiently simulated using a rewrite-based environment.

Mots clés

Fichier principal
Vignette du fichier
submission.pdf (262.5 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00173535 , version 1 (20-09-2007)
inria-00173535 , version 2 (12-10-2007)
inria-00173535 , version 3 (15-02-2008)
inria-00173535 , version 4 (26-04-2008)

Identifiants

  • HAL Id : inria-00173535 , version 2

Citer

Emilie Balland, Claude Kirchner, Pierre-Etienne Moreau. Term-graph rewriting via explicit paths. 2007. ⟨inria-00173535v2⟩
168 Consultations
201 Téléchargements

Partager

Gmail Facebook X LinkedIn More