White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Unification and equation solving in nilpotent groups and monoids

Burke, Edmund Kieran (1991) Unification and equation solving in nilpotent groups and monoids. PhD thesis, University of Leeds.

[img] Text
uk_bl_ethos_303430.pdf

Download (6Mb)

Abstract

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.

Item Type: Thesis (PhD)
Academic Units: The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds)
Depositing User: Ethos Import
Date Deposited: 04 Dec 2009 15:58
Last Modified: 08 Aug 2013 08:43
URI: http://etheses.whiterose.ac.uk/id/eprint/193

Actions (repository staff only: login required)