Addressed Term Rewriting Systems

Abstract : We propose Addressed Term Rewriting Systems (ATRS) as a solution to the still-standing problem of finding a simple yet formally useful framework that can account for computation with sharing, cycles, and side effects. ATRS are characterised by the combination of three features: they work with terms where structural induction is useful, they use a minimal ``back-pointer'' representation of cyclic data, and they ensure a bounded complexity of rewrite steps by eliminating implicit pointer redirection. In the paper we develop this and show how it is a very useful compromise between less abstract term graph rewriting and the more abstract equational rewriting.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02102103
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:14:17 AM
Last modification on : Sunday, April 28, 2019 - 1:23:08 AM

File

RR1999-30.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102103, version 1

Collections

Citation

Frédéric Lang, Daniel Dougherty, Pierre Lescanne, Kristoffer Rose. Addressed Term Rewriting Systems. [Research Report] LIP RR-1999-30, Laboratoire de l'informatique du parallélisme. 1999, 2+34p. ⟨hal-02102103⟩

Share

Metrics

Record views

14

Files downloads

12