A semi-Thue system $\mathfrak{S}$ is a pair $(\Sigma, P)$ where $\Sigma$ is an alphabet and $P$ is a non-empty finite binary relation on $\Sigma^*$ , the Kleene star of $\Sigma$ .

Elements of $P$ are variously called defining relations, productions, or rewrite rules, and $\mathfrak{S}$ itself is also known as a rewriting system. If $(x,y)\in P$ , we call $x$ the antecedent, and $y$ the consequent. Instead of writing $(x,y)\in P$ or $xPy$ , we usually write $$x\to y.$$

Let $\mathfrak{S}=(\Sigma,P)$ be a semi-Thue system. Given a word $u$ over $\Sigma$ , we say that a word $v$ over $\Sigma$ is immediately derivable from $u$ if there is a defining relation $x\to y$ such that $$u=rxs\qquad\mbox{ and }\qquad v=rys,$$ for some words $r,s$ (which may be empty) over $\Sigma$ . If $v$ is immediately derivable from $u$ , we write $$u\Rightarrow v.$$ Let $P'$ be the set of all pairs $(u,v)\in \Sigma^*\times \Sigma^*$ such that $u\Rightarrow v$ . Then $P\subseteq P'$ , and

If $u\Rightarrow v$ , then $wu\Rightarrow wv$ and $uw\Rightarrow vw$ for any word $w$ .

$a\derive b$ and $c\derive d$ imply $ac\derive bd$ .

Example. Let $\mathfrak{S}$ be a semi-Thue system over the alphabet $\Sigma=\lbrace a,b,c\rbrace$ , with the set of defining relations given by $P=\lbrace ab\to bc, bc \to cb \rbrace$ . Then words $ac^3b$ , $a^2c^2b$ and as $bc^4$ are all derivable from $a^2bc^2$ :

• $a^2bc^2 \Rightarrow a(bc)c^2 \Rightarrow ac(bc)c \Rightarrow ac^2(cb) = ac^3b$ ,
• $a^2bc^2 \Rightarrow a^2(cb)c \Rightarrow a^2c(cb) = a^2c^2b$ , and
• $a^2bc^2 \Rightarrow a(bc)c^2 \Rightarrow (bc)cc^2 = bc^4$ .

Remarks.

1. Given a semi-Thue system $\mathfrak{S}=(\Sigma,P)$ , one can associate a subset $A$ of $\Sigma^*$ whose elements we call axioms of $\mathfrak{S}$ . Any word $v$ that is derivable from an axiom $a\in A$ is called a theorem (of $\mathfrak{S}$ ). If $v$ is a theorem, we write $A \vdash_{\mathfrak{S}} v$ . The set of all theorems is written $L_{\mathfrak{S}}(A)$ , and is called the language (over $\Sigma$ ) generated by $A$ .
2. Let $\mathfrak{S}$ and $A$ be defined as above, and $T$ any alphabet. Call the elements of $T\cap \Sigma$ the terminals of $\mathfrak{S}$ . The set $$L_{\mathfrak{S}}(A)\cap T^*$$ is called the language generated by $A$ over $T$ , and written $L_{\mathfrak{S}}(A,T)$ . It is easy to see that $L_{\mathfrak{S}}(A,T)=L_{\mathfrak{S}}(A,T\cap \Sigma)$ .
3. A language $L$ over an alphabet $\Sigma$ is said to be generable by a semi-Thue system if there is a semi-Thue system $\mathfrak{S}$ and a finite set of axioms $A$ of $\mathfrak{S}$ such that $L= L_{\mathfrak{S}}(A,\Sigma)$ .
4. Semi-Thue systems are ``equivalent'' to formal grammars in the following sense:

   a language is generable by a formal grammar iff it is semi-Thue generable.

   The idea is to turn every defining relation $x\to y$ in $P$ into a production $SxT\to SyT$ , where $S$ and $T$ are non-terminals or variables. As such, a production of the form $SxT\to SyT$ is sometimes called a semi-Thue production.
5. Given a semi-Thue system $\mathfrak{S}=(\Sigma,P)$ , the word problem for $\mathfrak{S}$ asks whether or not for any pair of words $u,v$ over $\Sigma$ , one can determine in a finite number of steps (an algorithm) that $u\derive v$ . If such an algorithm exists, we say that the word problem for $\mathfrak{S}$ is solvable. It turns out there exists a semi-Thue system such that the word problem for it is unsolvable.
6. The word problem for a specific $\mathfrak{S}$ is the same as finding an algorithm to determine whether $v$ is a theorem based on a singleton axiom $\lbrace u\rbrace$ for arbitrary words $u,v$ .
7. The word problem for semi-Thue systems asks whether or not, given any semi-Thue system $\mathfrak{S}$ , the word problem for $\mathfrak{S}$ is solvable. From the previous remark, we see the word problem for semi-Thue systems is unsolvable.

Bibliography

1

M. Davis, Computability and Unsolvability. Dover Publications, New York (1982).

2

H. Hermes, Enumerability, Decidability, Computability: An Introduction to the Theory of Recursive Functions. Springer, New York, (1969).