Addressed Term Rewriting Systems
Frédéric Lang, Daniel Dougherty, Pierre Lescanne, Kristoffer H. Rose · 1999
We propose Addressed Term Rewriting Systems (ATRS) as a solution to the still-standing problem of nding a simple yet formally useful framework that can account for computation with sharing, cycles, and mutation. 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 rewriting 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.