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 PDF format:
PDF
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.