Semi-Thue System - Definition

Definition

A string rewriting system or semi-Thue system is a tuple where

• is an alphabet, usually assumed finite. The elements of the set (* is the Kleene star here) are finite (possibly empty) strings on, sometimes called words in formal languages; we will simply call them strings here.
• is a binary relation on strings from, i.e., Each element is called a (rewriting) rule and is usually written .

If the relation is symmetric, then the system is called a Thue system.

The rewriting rules on R can be naturally extended to other strings in by allowing substrings to be rewritten according to R. More formally, the one-step rewriting relation relation induced by R on for any strings s, and t in :

if and only if there exist x, y, u, v in such that s = xuy, t = xvy, and .

Since is a relation on, the pair fits the definition of an abstract rewriting system. Obviously R is a subset of . Some authors use a different notation for the arrow in (e.g. ) in order to distinguish it from R itself because they later want to be able to drop the subscript and still avoid confusion between R and the one-step rewrite induced by R.

Clearly in a semi-Thue system we can form a (finite or infinite) sequence of strings produced by starting with an initial string and repeatedly rewriting it by making one substring-replacement at a time:

A zero-or-more-steps rewriting like this is captured by the reflexive transitive closure of, denoted by (see abstract rewriting system#Basic notions). This is called the rewriting relation or reduction relation on induced by R.