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.

Principle

Computation and equational reasoning are modeled as directed applications of pattern-based equations: a rewrite step substitutes a matched instance of l by r under a matching substitution and context; properties such as termination (no infinite rewrite sequences) and confluence (unique normal forms) govern the determinacy and decidability of equality.

Demonstration

Simple TRS for arithmetic simplification: rules 0 + x → x, succ(x) + y → succ(x + y) rewrite expressions to a normal form. A terminating, confluent TRS yields a unique normal form for each term, so equivalence modulo the rewrite relation is decidable by normalizing both sides.

Misapplication

Using rewriting rules without checking termination can produce non-terminating reductions; ignoring confluence can lead to distinct normal forms depending on rewrite order, invalidating claims of decidability. Applying first-order TRS techniques to higher-order or context-sensitive languages without adaptation can misrepresent expressiveness and complexity.

Consequence

TRSs provide a uniform framework for defining computation, program transformation, algebraic specification, and automated equational reasoning; when termination and confluence hold, they give canonical computation and decidable word problems, and they connect to semantics (e.g., operational semantics) and to implementation techniques (term indexing, completion algorithms).

Reversal

Reversing a rewrite step turns directed computation into an equational step (r → l) and is the basis of completion procedures (e.g., attempting to make a set of equations confluent) or of inverse reduction; reversal highlights the difference between oriented computation and symmetric equational reasoning.

Boundary

Standard TRSs are first-order, unconditional, context-insensitive rule systems; extensions include conditional, context-sensitive, higher-order, and modulo-theory rewriting, each with different decidability and confluence/termination properties. Claims about uniqueness of normal form or decidability must specify the TRS class.

Semantic Tension

Tension exists between viewing rewriting as computation (directed, operational) and as proof of equality (symmetric, algebraic); there is also a trade-off between expressiveness (more features) and analyzability (termination/confluence proofs become harder).

Synthesis

A term rewriting system is a pattern-directed, rule-based model of computation and equational reasoning: by matching subterms and applying oriented substitutions according to rewrite rules, it transforms expressions; termination and confluence determine when rewriting yields canonical representations and decidable equality, while extensions adapt the framework to richer languages at the cost of complexity.