| 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 ∈ (X ∪ X-1)*, 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. |
