# Inverse Monoids Presented By a Single Sparse Relator

Steve Lindblad (spl -at- member -dot- fsf.org)

Ph.D. Dissertation

University of Nebraska--Lincoln

December 2003

Advisors: Susan Hermiller and John Meakin
Welcome to my web page. You will find information about my Ph.D. here.

My dissertation is available in the following formats:
PDF,
Postscript,
.ps.gz

The program *spar* determines whether or not a word
u equals 1 in an inverse monoid of the form M=Inv<X|w=1>, where
the relator w is a sparse word. The source code is available in
sparsrc.tar.gz. To use the
program, unpack the file (e.g., "tar xzf sparsrc.tar.gz"), change to
the sparsrc directory ("cd sparsrc"), and
compile *spar* by typing "make". To run the program,
type "spar" or "./spar".
You can also try downloading and running the
GNU/Linux executable (spar) directly, but you may
need to compile it yourself to make it work on your machine.

## Abstract

We study a class of inverse monoids of the form M=Inv<X|w=1>,
where the single relator w has a combinatorial property that we call
**sparse**.
For a sparse word w, we prove that the Schutzenberger complex
of the identity of M has a particularly nice topology. We analyze
the manner in which the Schutzenberger complex is constructed using an
iterative procedure, due to Stephen, analogous to the Todd-Coxeter
procedure. We define an appropriate notion of dual graph of the Schutzenberger
complex, and prove that this dual graph is a tree if w is sparse.
We use this tree to construct a pushdown automaton that encodes the
information contained in the Schutzenberger complex. This pushdown automaton
provides us with an algorithm that, given a word u,
determines whether or not u=1 in M. This, together with results
of Stephen and the fact due to Ivanov, Margolis, and Meakin that the
inverse monoid is E-unitary, shows that the word problem is solvable
for M. Finally, we provide an implementation, in the C++
programming language, of the algorithm to determine whether or not
u=1 in M.