Unification and equation solving in nilpotent groups and monoids

Unification and equation solving have been considered for groups [44], semigroups [43], abelian groups [39] and abelian semigroups [25], [33], [68], [69]. In this thesis we consider partially commutative groups and monoids. Nilpotency provides us with a partial commutativity condition in the case of groups. It is noted that unification in a theory is equivalent to equation solving in a free model of that theory if such a model exists. The unification algorithm for nilpotent groups G of class k works by passing to the quotient of G by the (k-1) th term of the lower central series and lifting the solution up the factors formed from G by the terms of the lower central series. There are certain unification problems, however, where this does not work as it stands and special treatment is required involving the solutions of a certain restricted class of diophantine equations of degree k. The unification problem for the theories of nilpotent groups of class Z5 is shown to be undecidable. This improves the result of Romankov [60] who showed it for class Z 9. The result is established by reducing the problem to that of algorithmically solving an arbitrary diophantine equation of degree 4. It is well known that this problem is undecidable [50], [60]. A special set of partially commutative monoids is introduced. An algorithm to solve equations in these monoids relative to solving certain systems of diophantine equations of degree 2 is given. These equations have similarities with those that occur for nilpotent groups of class 2.