The word problem of inverse monoids presented by one idempotent relator (Q1314383): Difference between revisions

The paper studies inverse semigroups presented by a finite set of generators \(X \cup X^{-1}\) and one relation \(e = 1\), where \(e\) represents an idempotent in the free inverse monoid, and 1 is the empty word. The word problem for inverse monoids is generally undecidable, but here the automaton approach of Stephen is used to prove that the decidability problem for words \(u\), \(v\) has complexity bounded by a cubic polynomial on the sum of the lengths of \(u\), \(v\) and \(e\), (if \(e\) is positively labelled, meaning that every vertex of its Munn tree is in \(X^*\), the complexity of the problem is linear). Moreover, it is shown that the set of words in the congruence class (in the free monoid) of \(u\) is a deterministic context-free language.