HAL - INRIA :: [inria-00173535, version 4] Term-graph rewriting via explicit paths

inria-00173535, version 4

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec acte</head>
<biblStruct type="inproceedings" xml:id="inria-00173535"><analytic>
<author><persName><forename>Emilie</forename><surname>Balland</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">PAREO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Pierre-Etienne</forename><surname>Moreau</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">PAREO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<title type="main" level="a">Term-graph rewriting via explicit paths</title></analytic><monogr><meeting>RTA: International Conference on Rewriting Techniques and Applications</meeting><imprint><publisher>Springer</publisher><pubPlace><settlement>Hagenberg</settlement><country>Autriche</country></pubPlace><biblScope type="publicationDate">2008</biblScope><biblScope type="vol">5117</biblScope><biblScope type="pp">32-47</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00173535/en/</idno><idno type="HALFile">http://hal.inria.fr/inria-00173535/PDF/longversion.pdf</idno></biblStruct>
</listBibl>
</listBibl>

Term-graph rewriting via explicit paths

Emilie Balland (

) ¹, Pierre-Etienne Moreau ¹

(2008)

Accès au texte intégral
PDF

RTA: International Conference on Rewriting Techniques and Applications 5117 (2008) 32-47

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.

1 :	PAREO (INRIA Lorraine - LORIA)
	INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine

Domaine

Informatique/Informatique et langage

Mots-clés : Term-graph rewriting

Versions disponibles :


inria-00173535, version 4
http://hal.inria.fr/inria-00173535/fr/
oai:hal.inria.fr:inria-00173535
Contributeur : Emilie Balland <>
Soumis le : Samedi 26 Avril 2008, 12:28:42
Dernière modification le : Mardi 4 Novembre 2008, 16:27:09