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

Principle

Rewrite rules of the form l -> r are applied to occurrences of instances of l in a larger term via matching and substitution; repeated application yields reduction sequences whose properties (termination, confluence) determine uniqueness and existence of normal forms.

Demonstration

With rules { f(a) -> b, f(x) -> g(x) } and term f(f(a)), one reduction applies f(a) -> b at the inner occurrence yielding f(b), then perhaps f(x) -> g(x) yields g(b); different rule application orders may affect results if the system is not confluent.

Misapplication

Expecting unique normal forms or termination in a TRS without verifying confluence or termination properties; applying rules ignoring variable capture or side conditions required by the rule format.

Consequence

When designed with desired properties, a TRS yields algorithmic normalization, decision procedures for equational theories, and operational semantics for programming languages and theorem provers.

Reversal

Invert the directed nature by treating rules as bidirectional equations (l ↔ r) to form an equational theory; this removes reduction directionality and shifts focus from computation to equality reasoning.

Boundary

Applies to first-order terms under a given signature and rule set; standard TRSs exclude higher-order binding constructs, side-effectful operations, or contextual constraints unless explicitly extended.

Semantic Tension

Tension between viewing rules as deterministic computational steps (rewriting) and viewing them as logical equalities (equations) where direction and strategy become secondary; both perspectives influence correctness criteria.

Synthesis

A Term Rewriting System is a syntactic engine composed of directed replacement rules that, by matching and substitution, compute term transformations; its usefulness depends on meta-properties like termination and confluence which control determinism and decidability.