New Bounds in Parallel Unification

MGU(k-depth) is the family of problems, which contains, for each natural k, MGU restricted to inputs with depth no greater than k. MGU(k-breadth) is the family which, for each natural k, contains MGU restricted to inputs with breadth no greater than k. We prove that, for each k>1, MGUK(k-depth) equivalent (in LogSpace reduction) to MGU, and also MGU(k-breadth) equivalent (in LogSpace reduction) to MGU. This shows that bounds either on the depth or on the breadth of the input do not significantly speed up the computation of unification on PRAM machines. The paper concludes with a look at the design of parallel unification algorithms, and at unification on flat inputs. As a final contribution, we introduce a new algorithm which improves the performance of known algorithms for parallel unification and also computes in polylog PRAM Time on flat inputs.