Thue system

A semi-Thue system $\mathfrak{S}=(\Sigma,R)$ is said to be a Thue system if $R$ is a symmetric relation  on $\Sigma^{*}$. In other words, if $x\to y$ is a defining relation in $R$, then so is $y\to x$.

Like a semi-Thue system, we can define the concepts  of immediately derivable and derivable pairs. Let $R^{\prime}$ and $R^{\prime\prime}$ be the respective collections  of these pairs. Since $R$ is symmetric, so is $R^{\prime}$ and consequently $R^{\prime\prime}$. Similarly, the notations are: for elements $(a,b)\in R^{\prime}$, we write $a\Rightarrow b$, and for elements $(c,d)\in R^{\prime\prime}$, we write $a\lx@stackrel{{\scriptstyle*}}{{\Rightarrow}}b$.

If we regard $\Sigma^{*}$ as a free monoid with concatenation  $\cdot$ as multiplication  and the empty word  $\lambda$ as the multiplicative identity  , then $\lx@stackrel{{\scriptstyle*}}{{\Rightarrow}}$ is a congruence relation  on $\Sigma^{*}$: it is an equivalence relation  and respects concatenation, meaning that if $a\lx@stackrel{{\scriptstyle*}}{{\Rightarrow}}b$ and $c\lx@stackrel{{\scriptstyle*}}{{\Rightarrow}}d$, then $ac\lx@stackrel{{\scriptstyle*}}{{\Rightarrow}}bd$. Therefore, we can take the quotent $\Sigma^{*}/\lx@stackrel{{\scriptstyle*}}{{\Rightarrow}}$ and the resulting set of equivalence classes  is again a monoid with $[\lambda]$ as the multiplicative identity. It is a monoid generated by $[a]$ whenever $a\in\Sigma$ with relations   $[u]=[v]$ whenever $u\to v$ is a defining relation in $R$. Thus, two elements are in the same equivalence class if one is derivable from another. Let us denote this monoid by $[\Sigma]_{\mathfrak{S}}$.

Now let $\mathfrak{S}=(\Sigma,R)$ be a Thue system. Then $\mathfrak{S}$ is called a group system if there exists an involution  ${}^{-1}$ on $\Sigma$ given by $a\mapsto a^{-1}$, and that for every $a\in\Sigma$, $aa^{-1}\to\lambda$ is a defining relation in $R$. Since ${}^{-1}$ is an involution, if $b$ is the symbol in $\Sigma$ such that $b=a^{-1}$, then $b^{-1}=a$. So $a^{-1}a=ba=bb^{-1}\to\lambda$ also. In fact, it is not hard to see that for a group system $\mathfrak{S}$, $[\Sigma]_{\mathfrak{S}}$ is the group with generators $[a]$ whenever $a\in\Sigma$ and with relators $[u][v]^{-1}$ whenever $u\to v$ is a defining relation in $R$. Every non-trivial element in $[\Sigma]_{\mathfrak{S}}$ has an expression $[a_{1}]^{p_{1}}\cdots[a_{n}]^{p_{n}}$, where each $a_{i}$ is a letter in $\Sigma$ such that it is distinct from its neighbors ($a_{i}\neq a_{i+1}$), and $p_{i}$ are non-zero integers. This expression is unique in the sense that it is “reduced”. See reduced words for more detail.

Remark. Like the word problem for semi-Thue systems, the word problem for Thue systems and group systems can be similarly posed. It can be shown that the word problem for Thue systems and group systems are both unsolvable. As a result, the corresponding word problems for semigroups  and for groups are also unsolvable.

References

Title Thue system ThueSystem 2013-03-22 17:33:19 2013-03-22 17:33:19 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 03D03 msc 03D40 msc 68Q42 msc 20M35 SemigroupWithInvolution group system