Rewriting reduction and pruning reduction on Munn trees
Kaicheng Wang · Lincoln (University of Nebraska) · 1996
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.