Skip to Main content Skip to Navigation

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 :
Complete list of metadata
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:14:17 AM
Last modification on : Saturday, September 11, 2021 - 3:19:16 AM


Files produced by the author(s)


  • HAL Id : hal-02102103, version 1



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⟩



Les métriques sont temporairement indisponibles