THE WORD PROBLEM FOR INVERSE MONOIDS PRESENTED BY ONE IDEMPOTENT RELATOR

We study inverse monoids presented by a finite set of generators and o ne relation e = 1, where e is a word representing an idempotent in the free inverse monoid, and 1 is the empty word. We show that (1) the wo rd problem is solvable by a polynomial-time algorithm; (2) every congr uence class (in the free monoid) with respect to such a presentation i s a deterministic context-free language. Such congruence classes can b e viewed as generalizations of parenthesis languages; and (3) the word problem is solvable by a linear-time algorithm in the more special ca se where e is a ''positively labeled'' idempotent.