ARM : abstract rewriting machine

Term rewriting is frequently used as implementation technique for algebraic specifications. In this paper we present the abstract term rewriting machine (ARM), which has an extremely compact instruction set and imposes no restrictions on the implemented TRSs. Apart from standard conditional term rewriting, associative lists are supported. ARM code is translated to (ANSI) C; the resulting execution speeds are good (on a sun4, an average of 80000 rewriting steps per second and a maximum of 416000 r/s were measured). Several benchmarks are shown, and related work is discussed in depth.