Definition
String rewriting is a formal model of computation in which a system has an alphabet, an initial string (or set of strings), and rules of the form lhs → rhs that license replacing any occurrence of lhs in a string with rhs. The MIU-system, the pq-system, TNT, Thue systems, and Markov algorithms are all string-rewriting systems. They are equivalent in power to Turing machines.
Why it matters
How it works
Define an alphabet, an initial string (axiom), and a list of substitution rules. To compute, find any rule whose left side matches a substring of the current string; replace that substring with the rule's right side. Repeat. The process terminates when no rule applies (some systems have explicit halt rules; others halt by reaching a normal form). Choices of which rule to apply when multiple match yield different evaluation strategies.