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.