TermRewriting

Term rewriting is a fundamental concept in computer science and logic that deals with the process of replacing subterms within a larger expression according to a set of predefined rules. These rules, often called rewrite rules or reduction rules, specify how a particular term can be transformed into another term. The core idea is that applying a rewrite rule to a term is an operation that yields a new, often simpler, term.

A term rewriting system (TRS) consists of a set of terms and a set of rewrite rules. The process of rewriting involves repeatedly applying these rules to a given term until no more rules can be applied. This final term is known as a normal form. The study of term rewriting systems focuses on properties like termination, which ensures that the rewriting process always finishes, and confluence, which guarantees that the order in which rules are applied does not affect the final result. If a system is both terminating and confluent, it is called strongly normalizing.

Applications of term rewriting are widespread. It is a key technique in automated theorem proving, symbolic computation systems (like computer algebra systems), and the analysis of functional programming languages. In logic, term rewriting is used to define and manipulate logical formulas. The concept also underpins formal verification methods, where complex systems are modeled and analyzed using rewrite rules to ensure correctness and safety. The simplicity and elegance of term rewriting make it a powerful tool for modeling computation and reasoning about systems.