6. Relating the Submonoid and Subalgebra Membership Problems in Monoids and Monoid Rings

While the subgroup problem is thoroughly studied in the literature, the submonoid problem is less investigated except for some special cases like the free monoid case. Submonoids in free monoids are used in the theory of codes, but codes (as regular languages) are usually studied using techniques from formal language theory. Since rewriting techniques are seldom used in this context, in this section we want to introduce appropriate notions for describing submonoids of monoids to give an analogon to the approach presented for subgroups of groups..

Definition 12   Given a submonoid ${\cal U}$ of a monoid ${\cal M}$, the submonoid problem is to determine, given $w \in {\cal M}$, whether $w \in {\cal U}$.

Given a finite subset S of a monoid ${\cal M}$, we let $\left< S \right> = \{ s_1 \circ\ldots \circ s_n \mid n \in {\bf N}, s_i \in S \}$ denote the submonoid generated by S. A submonoid ${\cal U}$ of a monoid ${\cal M}$ is called finitely generated if there exists a finite subset S of ${\cal M}$ such that ${\cal U}= \left< S \right>$.

In the previous section we have seen how the subgroup problem is related to the membership problem for right respectively left ideals in group rings. Unfortunately, theorem 9 cannot be generalized for the submonoid problem as the following example shows:

Example 13   Let $\Sigma = \{ a,b \}, T = \{ ab \longrightarrow\lambda \}$ be a string rewriting system presenting of a monoid ${\cal M}$, the bicyclic monoid. Let ${\cal U} = \{ a^n \mid n \in {\bf N}\}$ be the submonoid of ${\cal M}$ generated by $S= \{ a \}$. Then we have $b-1 \in {\sf ideal}_{r}^{}(P_S)$ since $b-1 = -1 \cdot(a-1) \ast b$ but $b \not\in {\cal U}$. Theorem 9 would lead to $b \in {\cal U}$.

The problem shown in this example is due to the following observation: As in the subgroup case, a submonoid ${\cal U}$ of a monoid ${\cal M}$ induces a right congruence on ${\cal M}$ by setting

$$u \sim_{{\cal U}} v \mbox{ if and only if } {\cal U}u = {\cal U}v$$

for $u,v \in {\cal M}$. But the submonoid itself in general is no longer the right congruence class $[ \lambda ]_{\sim_{\cal U}}$. In our example we find that $b \in [ \lambda ]_{\sim_{\cal U}}$ while $b \not\in {\cal U} = \{ a^n \mid n \in {\bf N}\}$. Hence the submonoid cannot be described adequately in the monoid ring using the right ideal congruence as in the subgroup case studied before. But there is another algebraic substructure of monoid rings which is appropriate to restate the submonoid problem in algebraic terms - the subalgebra.

Definition 14   A nonempty subset S of ${\bf K}[{\cal M}]$ is called a subalgebra of ${\bf K}[{\cal M}]$, if the following hold:

1.

${\bf K}\subseteq S$,

2.

for all $f,g \in S$ we have $f-g \in S$, and

3.

for all $f,g \in S$ we have $f \ast g \in S$.

Notice how the third condition differs from the definition of ideals. For a subset $P \subset {\bf K}[{\cal M}]$ let ${\sf subalgebra}(P)$ denote the minimal subalgebra of ${\bf K}[{\cal M}]$ containing P. The next theorem states that the submonoid problem for a monoid is equivalent to a special instance of the subalgebra membership problem in the corresponding monoid ring.

Theorem 15   Let S be a subset of ${\cal M}$ and $P_S = \{ s - 1 \mid s \in S \}$ a subset of ${\bf K}[{\cal M}]$ associated to S. Then the following statements are equivalent:

(1)

$w \in \left< S \right>$.

(2)

$w- 1 \in {\sf subalgebra}(P_S)$.

Proof : 1.11.1 
$1 \Longrightarrow2:$