3. Relating the Word and the Ideal Membership Problems in Monoids and Free Monoid Rings

Let us start this section with some algebraic notions concerning monoid rings. For a monoid ${\cal M}$ with multiplication $\circ$ and a total well-founded ordering $\succeq$ on ${\cal M}$, the elements of the monoid ring ${\bf K}[{\cal M}]$ over a field ${\bf K}$ can be presented as ``polynomials'' $f = \sum_{t \in {\cal M}} \alpha_{t} \cdot t$ where only finitely many $\alpha_t \in {\bf K}$ are non-zero. The elements $\alpha_t \cdot t$ are called monomials consisting of a coefficient $\alpha_t$ and a term t. Addition and multiplication for two polynomials $f = \sum_{t \in {\cal M}} \alpha_{t} \cdot t$ and $h = \sum_{t \in {\cal M}} \beta_{t} \cdot t$ is defined as $f + h = \sum_{t \in {\cal M}} (\alpha_{t} + \beta_{t}) \cdot t$ and $f \ast h = \sum_{t \in {\cal M}} \gamma_{t} \cdot t$ with $\gamma_{t} = \sum_{x \circ y = t } \alpha_{x} \cdot\beta_{y}$. Given a non-zero polynomial p in ${\bf K}[{\cal M}]$, the head term ${\sf HT}(p)$ is the largest term in p with respect to $\succ$, which has non-zero coefficient denoted by ${\sf HC}(p)$, and the head monomial is ${\sf HM}(p) = {\sf HC}(p) \cdot{\sf HT}(p)$. ${\sf T}(p)$ is the set of all $t \in {\cal M}$ with non-zero coefficient in p. For a subset F of ${\bf K}[{\cal M}]$ we call the set ${\sf ideal}_{r}^{}(F) = \{ \sum_{i=1}^n \alpha_i \cdot f_i \ast w_i \mid n \in {\bf N}, \alpha_i \in {\bf K}, f_i \in F, w_i \in {\cal M}\}$⁵ the right ideal, ${\sf ideal}_{l}^{}(F) = \{ \sum_{i=1}^n \alpha_i \cdot w_i \ast f_i \mid n \in {\bf N}, \alpha_i \in {\bf K}, f_i \in F, w_i \in {\cal M}\}$ the left ideal and ${\sf ideal}_{}^{}(F) = \{ \sum_{i=1}^n \alpha_i \cdot u_i \ast f_i \ast w_i \mid n \in {\bf N}, \alpha_i \in {\bf K}, f_i \in F, u_i, w_i \in {\cal M}\}$ the two-sided ideal generated by F. By $\equiv_{\mathfrak{i}}$ we will denote the (right, left respectively two-sided) congruence induced by a (right, left respectively two-sided) ideal $\mathfrak{i}$ on ${\bf K}[{\cal M}]$.

The following theorem states that the word problem for monoids is equivalent to a restricted version of the ideal membership problem in free monoid rings. This immediately implies the undecidability of the latter problem which is also stated in [Mo87,KaWe90], but the proof we give here provides a stronger result outlined below. For a string rewriting system $(\Sigma,T)$ presenting a monoid, the related free monoid ring is ${\bf K}[\Sigma^*]$, where $\Sigma^*$ is the free monoid generated by $\Sigma$ with word concatenation as binary operation and $\lambda$ as identity element.

Theorem 1   Let $(\Sigma,T)$ be a finite string rewriting system presenting a monoid ${\cal M}$ and $P_T= \{ l-r \mid (l,r) \in T \}$ a set of polynomials in ${\bf K}[\Sigma^*]$ associated with T.
Then for $u,v \in \Sigma^*$ the following statements are equivalent:

(1)

$u \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } v$, i.e. the relation u=v holds in ${\cal M}$.

(2)

$u-v \in {\sf ideal}_{}^{}(P_T)$.

Proof : 1.11.1 
$1 \Longrightarrow2:$