Minimal term rewriting systems
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.
|Processors (acm D.3.4), Applicative Programming (acm D.1.1), Logic Programming (acm D.1.6)|
|Compilers and interpreters (msc 68N20), Models of computation (Turing machines, etc.) (msc 68Q05), Grammars and rewriting systems (msc 68Q42), Abstract data types; algebraic specification (msc 68Q65)|
|Department of Computer Science [CS]|
|Organisation||Extensible programming environments|
Walters, H.R, & Kamperman, J.F.T. (1995). Minimal term rewriting systems. Department of Computer Science [CS]. CWI.