Next: 3. The General Case Up: Solving One-Sided Equations in Previous: 1. Introduction

# 2. The Special Case of One Equation

Let and be the equation we want to solve. In order to describe the generating set of solutions we have to find one solution of the inhomogeneous equation
 (1)

and if possible a finite set of generators for the solutions of the homogeneous equation
 (2)

The set of solutions of equation 2 forms a right -module which is called the right module of syzygies of according to the term used for ordinary Gröbner bases in the literature (see e.g. [2]). To find a generating set for this right module we proceed as suggested in [1]:
1. Let be a finite reduced prefix Gröbner basis of the right ideal generated by in , and , corresponding vectors. There are two linear mappings given by matrices1 , such that and .
2. Equation 1 is solvable if and only if . This is equivalent to and the reduction sequence gives rise to a representation where . Then, as , we get and is such a solution of equation 1.
3. Let be a generating set for the solutions of the homogeneous equation
 (3)

and let be the identity matrix. Further let be the columns of the matrix . Since these are solutions of the homogeneous equation 2 as well. We can even show that the set generates all solutions of 2:
Let be an arbitrary solution of equation 2, i.e.  . Then is a solution of equation 3 as . Hence there are such that . Further we find

and hence is a right linear combination of elements in .
Now the important part is to find a generating set for the solutions of the homogeneous equation 3. Let be a finite reduced prefix Gröbner basis of the right ideal generated by and let , for . In [1] the following situations define a set of generating zeros:

For every such that is a prefix (as a word) of , i.e.  for some , by Lemma 8 (see Section 5) we know for some . We determine vectors as follows:

where the polynomials are due to the reduction sequence .
Then , where

, is a solution of 3 as .

If no such polynomials exist in , Baader concluded that the homogeneous equation 3 in the free monoid ring had no solution. This is no longer true for arbitrary monoid rings.

Example 1   Let be a monoid ring where is presented by the string rewriting system , . Then for the homogeneous equation

we find that the set is a reduced prefix Gröbner basis of the right ideal it generates. Moreover neither of the head terms of the polynomials in this basis is prefix of the other. Still the equation can be solved: is a solution since .

This phenomenon is due to the fact that in most monoid rings s-polynomials are not sufficient for a Gröbner basis test. In [6] such a test for monoid rings as described here is presented. Besides testing s-polynomials the following test set has to be considered2:

For let for some . Additionally, we define vectors for and as follows: Let . For every we know as is a prefix Gröbner basis. Then , where

, is a solution of equation 3 as .

Lemma 2   The finitely many vectors , , form a right generating set for all solutions of equation 3.

Proof : 1.1
Let be an arbitrary (non-trivial) solution of 3. Let be the maximal term when concatenating the head terms of the multiples in the sum and the number of multiples with . A solution is called smaller than if either or and . We will prove our claim by induction on and 3. Since we assume to be a non-trivial solution, we know . Then we can distinguish two cases:
1. If there is such that , then , , and for some , . Then with

, is again a solution of 3. It remains to show that it is a smaller one. To see this we have to examine the multiples for all . Remember that since we get as the arise from the reduction sequence .
1. For we get and as and the resulting monomials add up to zero we get .
2. For we get and either if or else .
Hence either or is decreased.
2. Let us now assume there are such that . Without loss of generality we can assume that for some . Then by Lemma 8 we know that for some . For the corresponding s-polynomial we have a vector and we can define where with

. It remains to show that this solution indeed is smaller. To do this we examine the multiples for all .
1. For we get and by Lemma 8 . Hence implying either if or else .
2. For we get . Since we find .
3. For we get . Hence either if or .
Hence we find that either or in case , . Therefore, in all cases the solution derived from is smaller and we can show our claim by induction.

Next: 3. The General Case Up: Solving One-Sided Equations in Previous: 1. Introduction
| ZCA Home | Reports |