Minimal term rewriting systems
H. R. J. Walters, Jasper F.T Kamperman · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1995
Formally well-founded compilation techniques for Term Rewriting Systems (TRSs) are presented. TRSs are compiled into Minimal Term Rewriting Systems (MTRSs), a subclass of TRSs in which all rules have an extremely simple form. A notion of simulation of (rewrite) relations is presented, under which an MTRSs can be said to simulate a TRS. The MTRS rules can be directly interpreted as instructions for an extremely simple Abstract Rewriting Machine (ARM). Favourable practical results have already been obtained with an earlier version of ARM. CR Subject Classification (1991): D.3.4 [Programming languages]: Processors -- Compilers; D.1.1 [Programming Techniques]: Applicative (Functional) Programming; D.1.6: Logic Programming. AMS Subject Classification (1991): 68N20: Compilers and generators; 68Q05: Models of Computation; 68Q42: Rewriting Systems; 68Q65: Abstract data types; algebraic specification. Keywords & Phrases: minimal term rewriting systems, program transformation. Note: This re...