Term-graph rewriting via explicit paths

Emilie Balland 1 Pierre-Etienne Moreau 1
1 PAREO - Formal islands: foundations and applications
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Communication dans un congrès
Andrei Voronkov. RTA: International Conference on Rewriting Techniques and Applications, Jun 2008, Hagenberg, Austria. Springer, 5117, pp.32-47, 2008, Lecture Notes in Computer Science; RTA
Liste complète des métadonnées


https://hal.inria.fr/inria-00173535
Contributeur : Emilie Balland <>
Soumis le : samedi 26 avril 2008 - 12:28:42
Dernière modification le : mardi 25 octobre 2016 - 16:57:19
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 22:36:47

Fichier

longversion.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00173535, version 4

Collections

Citation

Emilie Balland, Pierre-Etienne Moreau. Term-graph rewriting via explicit paths. Andrei Voronkov. RTA: International Conference on Rewriting Techniques and Applications, Jun 2008, Hagenberg, Austria. Springer, 5117, pp.32-47, 2008, Lecture Notes in Computer Science; RTA. <inria-00173535v4>

Partager

Métriques

Consultations de
la notice

279

Téléchargements du document

124