Efficient solution of some problems in free partially commutative monoids (Q2640345)

A partially commutative alphabet is a pair (\(\Sigma\),\(\theta\)) consisting of a finite alphabet \(\Sigma\) and a binary relation \(\theta\) in \(\Sigma\) which gives the pairs of commuting letters. The free partially commutative monoid M(\(\Sigma\),\(\theta\)) determined by (\(\Sigma\),\(\theta\)) is the quotient monoid \(\Sigma^*/\equiv\), where \(\equiv\) is the congruence generated by \(\theta\). The authors present and analyze linear-time algorithms for several basic combinatorial problems concerning such monoids. In the following brief descriptions of the main questions considered, a fixed monoid M(\(\Sigma\),\(\theta\)) is assumed. (1) A nonempty word \(y\) is primitive mod \(\theta\), if there is no word \(z\) such that \(y\equiv z^{k}\) for some \(k>1\). If \(x\equiv y^{n}\) and \(y\) is primitive mod \(\theta\), then \(y\) is a congruential root of \(x\). Such a root can be found in time linear in the length of \(x\). Also, the related question whether two given words have some \(\equiv\)-congruent powers can be answered in linear time. (2) The generalized pattern-matching problem asks whether a word \(y\) is congruent to a factor of another given word \(x\). For this problem a linear-time algorithm which makes use of the Knuth-Morris-Pratt algorithm is given. (3) Two words \(x\) and \(y\) are conjugate in the free monoid \(\Sigma^*\) if \(xz = zy\) for some word \(z\), or equivalently, if there are words \(u\) and \(v\) such that \(x = uv\) and \(y = vu\). In the more general case at hand, these two definitions lead to different concepts, but for both of them linear-time algorithms deciding conjugacy are given. The paper is very well written and the extensive background knowledge used in the algorithms is also clearly presented.