Term Rewriting System

A formal system consisting of terms built from function symbols and variables together with a set of directed rewrite rules of the form l → r that replace instances of a left-hand pattern l by the corresponding right-hand term r; rewriting proceeds by repeatedly matching and replacing subterms.

A formal system consisting of a set of directed rewrite rules used to transform terms into other terms by pattern-directed replacement and substitution.