Partially commutative inverse monoids. (Q958191)

The paper studies complexity problems of free partially commutative inverse monoids. The word problem was shown to be decidable for these monoids in the thesis of Veloso da Costa. The present authors show that the complexity of the word problem is in \(O(n\log(n))\) on a random access machine. To obtain this bound the paper gives a new construction of free partially commutative inverse monoids by considering closed subsets for a closure operation on subsets of graph groups (or free partially commutative groups, or right-angled Artin groups). The submonoid membership problem asks whether an element of the monoid is in a given f.g.~submonoid. This problem is shown to be NP-hard for 2-generator free inverse monoid. In the latter part of the paper the authors study free partially commutative inverse monoids modulo finite idempotent presentations (a set of relations involving only idempotent elements). It is shown that the resulting quotient monoid has decidable word problem if and only if the dependence relation, associated to the partial commutation relation, is transitive. Finally, complexity bounds are considered in the transitive case.