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
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 ,
we let
denote
the submonoid generated by *S*.
A submonoid
of a monoid
is called **finitely generated**
if there exists a finite subset *S* of
such that
.

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

for . But, we can no longer characterize the submonoid by a special congruence class of this right congruence as the following example shows:

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

We can define the block containing , called , recursively as follows:

- .

Notice that when in defining *B*_{i}, if some *x* are used in extending *B*_{i-1}
because there are
such that
,
then
as well since we have
.

Reviewing the case of the bicyclic monoid in Example 5 we get
since for
we have
and hence
.
Procedure GENERALIZED TC SIMULATION computes the sets
and
.
On the other hand, if we look at the submonoid generated by *b* we get
and procedure GENERALIZED TC SIMULATION
computes the infinite sets
and
.

In order to link for some generating set *S* the block
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
on
and the congruences of (one-sided) ideals
generated by sets of binomials
in
(see e.g. [8]).
Using this fact, we get the following algebraic characterization of
in terms of right ideals in monoid rings.

- (1)
- .
- (2)
- .

- (1)
- .
- (2)
- .