The word problem for free partially commutative, partially associative groupoids (Q1329183)

A free partially commutative, partially associative groupoid is constructed in the following way. We take a finite set \(\Sigma\) of generators and its subset \(N\) which will generate the left nucleus. (The left nucleus of a groupoid \(G\) is \(N(G)=\{g \in G \mid (gx)y=g(xy),\;\forall x, y\}\).) Further a symmetric binary relation \(\theta\) on \(N\) is taken; \((a_ i,a_ j) \in \theta\) means \(a_ i a_ j=a_ j a_ i\). Then the groupoid \(G(\Sigma, N, \theta)\) obtained from the free groupoid on \(\Sigma\) by considering the left nucleus generated by \(N\) and the relation \(\theta\) is called a free partially commutative, partially associative groupoid. In the paper it is stated that the word problem for each \(G(\Sigma,N,\theta)\) is decidable in linear time.