8. TC in Monoids

Notice that procedure GENERALIZED TC SIMULATION in fact can also be applied to monoids by giving as input a string rewriting system $(\Sigma, T)$ where T no longer needs to contain the inverse rules. The question now is, what does the procedure compute in this more general setting?

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 \mathbb{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>$.

As in group theory we can define a right congruence as follows:

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

for $u,v \in {\cal M}$. But, we can no longer characterize the submonoid by a special congruence class of this right congruence as the following example shows:

Example 5   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 \mathbb{N}\}$ be the submonoid of ${\cal M}$ generated by $S= \{ a \}$. For the right congruence class of $\lambda$ we find $[ \lambda ]_{\sim_\mathcal{U}} = \{ \lambda \}$, i.e. even $a \not\in [ \lambda ]_{\sim_\mathcal{U}}$, while $\mathcal{U} = \{ a^n \mid n \in \mathbb{N}\}$.

So when defining ``cosets'' of submonoids in monoids we meet the difficulty that they no longer have such nice properties as cosets of subgroups in groups have. In [12] Neumann gives a different structure which is as close as possible with respect to the desired properties: Instead of adopting the analogue of a single coset of a subgroup in a group, he looks at the set of all cosets: Given a right congruence on monoids, i.e. an equivalence relation that admits right multiplication by elements of the monoid, the equivalence classes are called blocks. If B is such a block, then the elements $m \in {\cal M}$ such that $Bm \subseteq B$ form a submonoid of ${\cal M}$ called the fixing submonoid of B. Different non-void fixing submonoids that arise from the blocks of a right congruence can then be considered as conjugate.

Now starting with a submonoid ${\cal H}$ of ${\cal M}$ we are looking for the least right congruence that contains ${\cal H}$ in a block: then ${\cal H}$ will be contained in the fixing submonoid of that block⁷. This is the nearest one can get to ``cosets'' of ${\cal H}$ in ${\cal M}$.

We can define the block containing ${\cal H}$, called $B_{{\cal H}}$, recursively as follows:

• $B_0 = {\cal H}$
• $B_i = B_{i-1} \cup \{ b \circ x \mid b \in B_{i-1}, x \in {\cal M}\mbox{ s.t.~there exist } b_1, b_2 \in B_{i-1} \mbox{ with } b_1 = b_2 \circ x \}$
• $B_{{\cal H}} = \bigcup_{i \in \mathbb{N} } B_i$.

Of course if ${\cal H}$ is a subgroup of a group ${\cal M}$, then $B_{{\cal H}} = {\cal H}$ as $b_1 = b_2 \circ x$ implies $x = b_2^{-1} \circ b_1 \in {\cal H}$.

Notice that when in defining B_i, if some x are used in extending B_i-1 because there are $b_1, b_2 \in B_{i-1}$ such that $b_1 = b_2 \circ x$, then $x \in B_i$ as well since we have $\lambda \in B_0$.

Reviewing the case of the bicyclic monoid in Example 5 we get $B_{\langle a \rangle} = {\cal M}$ since for $i,j \in \mathbb{N}$ we have $a^i \circ b^ia^j = a^j \in \langle a \rangle = B_0$ and hence $b^ia^j \in B_{\langle a \rangle}$. Procedure GENERALIZED TC SIMULATION computes the sets $N = \{ \lambda \}$ and $G = \{ a \longrightarrow\lambda, b \longrightarrow\lambda \}$. On the other hand, if we look at the submonoid generated by b we get $B_{\langle b \rangle} = \{ b^n \mid n \in \mathbb{N}\}$ and procedure GENERALIZED TC SIMULATION computes the infinite sets $N = \{ a^n \mid n \in \mathbb{N}\}$ and $G = \{ a^{n+1}b \longrightarrow a^n \mid n \in \mathbb{N}\} \cup \{ b \longrightarrow\lambda \}$.

In order to link for some generating set S the block $B_{\langle S \rangle}$ to procedure GENERALIZED TC SIMULATION, we need the algebraic structure of one-sided ideals in monoid rings. It is easy to show that there is a one to one correspondence between the congruences generated by sets of rules $\{ \ell_i \longrightarrow r_i \mid 1 \leq i \leq n \}$ on $\Sigma^*$ and the congruences of (one-sided) ideals generated by sets of binomials $\{ \ell_i - r_i \mid 1 \leq i \leq n \}$ in $\mathbb{K} [\Sigma^*]$ (see e.g. [8]). Using this fact, we get the following algebraic characterization of $B_{\langle S \rangle}$ in terms of right ideals in monoid rings.

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

(1)

$w \in B_{\langle S \rangle}$.

(2)

$w- 1 \in {\sf ideal}_{r}^{\mathbb{K} [{\cal M}]}(P_S)$.

Exploiting the connections between string rewriting systems and special binomial ideal bases, it follows that on termination the set G computed by procedure GENERALIZED TC SIMULATION corresponds to a prefix Gröbner basis $\{ \ell - r \mid \ell \longrightarrow r \in G \}$ of the right ideal generated by the set P_S in $\mathbb{K} [{\cal M}]$ where ${\cal M}$ is the monoid presented by the string rewriting system $(\Sigma, T)$ (see [13,8] for more details):

Corollary 7   For S a subset of $\Sigma^*$ let $P_S = \{ s - 1 \mid s \in S \}$ and for T let $P_T = \{ x\ell - xr \mid x \in \Sigma^*, \ell \longrightarrow r \in T, \mbox{ no proper prefix of } x\ell \mbox{ is } \longrightarrow_T-\mbox{reducible} \}$. Then the following statements are equivalent:

(1)

$w \in B_{\langle S \rangle}$.

(2)

$w- 1 \in {\sf ideal}_{r}^{\mathbb{K} [\Sigma^*]}(P_S \cup P_T)$.

Moreover, if procedure GENERALIZED TC SIMULATION terminates on input S and T with output G, then $w \in B_{\langle S \rangle}$ if and only if $w \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$ } 1$.