Abstract Rewriting Systems

Overview

In an abstract rewriting system (ARS), an object is said to be in normal form if it cannot be rewritten any further, i.e. it is irreducible. An object is said to be in canonical form if it is presented in the "standard" representation (where "standard" is defined per field).

Examples of normal form include:

• Conjunctive Normal Form
• Disjunctive Normal Form
• Prenex Normal Form
• β-normal forms

In most fields, a canoncial form specifies a unique representation.

Confluence

Confluence is the property of rewriting systems describing which terms in such a system can be rewritten in more than one way while still yielding the same result.

For example, $(11+9)\times (2+4)$ is equivalently expressed as either $$20 \times (2 + 4) \quad\text{or}\quad (11 + 9) \times 6.$$

Either way, the final result of $20\times 6=120$ is reached.