Rewriting reduction and pruning reduction on Munn trees

We introduce the processes of rewriting reduction and pruning reduction on Munn trees (finite birooted trees with labelled edges) and use them to develop a general strategy to solve the idempotent word problem for inverse monoid presentations. The process of rewriting reduction on Munn trees is a generalization of the standard processes of rewriting on strings that is widely studied in computer science. The process of pruning reduction is a geometric adaptation of the process of rewriting reduction on Munn trees and is introduced as a natural way to deal with Munn trees, which may be viewed as two dimensional structures. The main part of the dissertation is devoted to a class of inverse monoid presentations of the form $M = INM\langle X\vert e = 1\rangle$ where X is a finite set and e is a word over $X \cup X\sp{-1}$ whose reduced form is 1. In this setting we present a quadratic time algorithm to solve the word problem for M. We also find normal forms in terms of reduced trees for the elements of M and show that the maximal subgroups of such a monoid are free groups of finite rank