Partially commutative inverse monoids.

Free partially commutative inverse monoids are investigated. As in the case of free partially commutative monoids or groups ( trace monoids or graph groups), free partially commutative inverse monoids are defined as quotients of free inverse monoids modulo a partially defined commutation relation on the generators. A quasi linear time algorithm for the word problem is presented. More precisely, we give an $\mathcal {O}(n\log(n))$ algorithm for a RAM. $\mathsf {NP}$ -completeness of the submonoid membership problem (also known as the generalized word problem) and the membership problem for rational sets is shown. Moreover, free partially commutative inverse monoids modulo a finite idempotent presentation are studied. It turns out that the word problem is decidable if and only if the complement of the partial commutation relation is transitive. [ABSTRACT FROM AUTHOR]