##  [Term Rewriting System](/term-rewriting-system-0) 

 Definition

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

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

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

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

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

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

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

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

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.