Next: 7. Concluding Remarks Up: Relating Rewriting Techniques on Previous: 5. Relating the Generalized

# 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 of a monoid , the submonoid problem is to determine, given , whether .

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 .

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 be a string rewriting system presenting of a monoid , the bicyclic monoid. Let be the submonoid of generated by . Then we have since but . Theorem 9 would lead to .

The problem shown in this example is due to the following observation: As in the subgroup case, a submonoid of a monoid induces a right congruence on by setting

for . But the submonoid itself in general is no longer the right congruence class . In our example we find that while . 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 is called a subalgebra of , if the following hold:
1.
,
2.
for all we have , and
3.
for all we have .

Notice how the third condition differs from the definition of ideals. For a subset let denote the minimal subalgebra of 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 and a subset of associated to S. Then the following statements are equivalent:
(1)
.
(2)
.

Proof : 1.11.1

Next: 7. Concluding Remarks Up: Relating Rewriting Techniques on Previous: 5. Relating the Generalized
| ZCA Home | Reports |