semi-Thue system

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

Elements of $P$ are variously called defining relations, productions, or rewrite rules, and $𝔖$ 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 $𝔖=(\mathrm{\Sigma },P)$ be a semi-Thue system. Given a word $u$ over $\mathrm{\Sigma }$, we say that a word $v$ over $\mathrm{\Sigma }$ is immediately derivable from $u$ if there is a defining relation $x\to y$ such that

$$u=rxs\mathit{\hspace{1em}\hspace{1em}}\text{ and }\mathit{\hspace{1em}\hspace{1em}}v=rys,$$

for some words $r,s$ (which may be empty) over $\mathrm{\Sigma }$. If $v$ is immediately derivable from $u$, we write

$$u\Rightarrow v.$$

Let $P^{\prime }$ be the set of all pairs $(u,v)\in {\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}$ such that $u\Rightarrow v$. Then $P\subseteq P^{\prime }$, and

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

Next, take the reflexive transitive closure $P^{\prime \prime }$ of $P^{\prime }$. Write $a\stackrel{*}{\Rightarrow }b$ for $(a,b)\in P^{\prime \prime }$. So $a\stackrel{*}{\Rightarrow }b$ means that either $a=b$, or there is a finite chain $a=a_1,\mathrm{\dots },a_n=b$ such that $a_i\Rightarrow a_{i+1}$ for $i=1,\mathrm{\dots },n-1$. When $a\stackrel{*}{\Rightarrow }b$, we say that $b$ is derivable from $a$. Concatenation preserves derivability:

$a\stackrel{*}{\Rightarrow }b$ and $c\stackrel{*}{\Rightarrow }d$ imply $ac\stackrel{*}{\Rightarrow }bd$.

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

• $a^{2}b{c}^2\Rightarrow a(bc)c^2\Rightarrow ac(bc)c\Rightarrow a{c}^2(cb)=a{c}^{3}b$,

• $a^{2}b{c}^2\Rightarrow a^2(cb)c\Rightarrow a^{2}c(cb)=a^2{c}^{2}b$, and

• $a^{2}b{c}^2\Rightarrow a(bc)c^2\Rightarrow (bc)c{c}^2=b{c}^4$.

Under $𝔖$, we see that if $v$ is derivable from $u$, then they have the same length: $|u|=|v|$. Furthermore, if we denote ${|a|}_u$ the number of occurrences of letter $a$ in a word $u$, then ${|a|}_v\le {|a|}_u$, ${|c|}_v\ge {|c|}_u$, and ${|b|}_v={|b|}_u$. Also, in order for a word $u$ to have a non-trivial word $v$ (non-trivial in the sense that $u\ne v$) derivable from it, $u$ must have either $ab$ or $bc$ as a subword. Therefore, words like $a^3$ or $c^3{b}^4{a}^2$ have no non-trivial derived words from them.

Remarks.

1. Given a semi-Thue system $𝔖=(\mathrm{\Sigma },P)$, one can associate a subset $A$ of ${\mathrm{\Sigma }}^{*}$ whose elements we call axioms of $𝔖$. Any word $v$ that is derivable from an axiom $a\in A$ is called a theorem (of $𝔖$). If $v$ is a theorem, we write $A{⊢}_{𝔖}v$. The set of all theorems is written $L_{𝔖}(A)$, and is called the language (over $\mathrm{\Sigma }$) generated by $A$.

2. Let $𝔖$ and $A$ be defined as above, and $T$ any alphabet. Call the elements of $T\cap \mathrm{\Sigma }$ the terminals of $𝔖$. The set

   $$L_{𝔖}(A)\cap T^{*}$$

   is called the language generated by $A$ over $T$, and written $L_{𝔖}(A,T)$. It is easy to see that $L_{𝔖}(A,T)=L_{𝔖}(A,T\cap \mathrm{\Sigma })$.

3. A language $L$ over an alphabet $\mathrm{\Sigma }$ is said to be generable by a semi-Thue system if there is a semi-Thue system $𝔖$ and a finite set of axioms $A$ of $𝔖$ such that $L=L_{𝔖}(A,\mathrm{\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 $𝔖=(\mathrm{\Sigma },P)$, the word problem for $𝔖$ asks whether or not for any pair of words $u,v$ over $\mathrm{\Sigma }$, one can determine in a finite number of steps (an algorithm) that $u\stackrel{*}{\Rightarrow }v$. If such an algorithm exists, we say that the word problem for $𝔖$ 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 $𝔖$ is the same as finding an algorithm to determine whether $v$ is a theorem based on a singleton axiom $\{u\}$ for arbitrary words $u,v$.

7. The word problem for semi-Thue systems asks whether or not, given any semi-Thue system $𝔖$, the word problem for $𝔖$ is solvable. From the previous remark, we see the word problem for semi-Thue systems is unsolvable.