Rewrite order

Rewriting s to t by a rule l::=r. If l and r are related by a rewrite relation, so are s and t. A simplification ordering always relates l and s, and similarly r and t.

In theoretical computer science, in particular in automated reasoning about formal equations, reduction orderings are used to prevent endless loops. Rewrite orders, and, in turn, rewrite relations, are generalizations of this concept that have turned out to be useful in theoretical investigations.