On two problems related to cancellativity (Q1070349)

The following two decision problems, that are related to the properties of right-cancellativity and left-cancellativity, respectively, of the monoid \({\mathfrak M}_ T\) defined by the presentation (\(\Sigma\) ;T), are investigated: Instance: A finite presentation (\(\Sigma\) ;T), and two words \(u,v\in \Sigma^*\). (1) Question: Does there exist a word \(x\in \Sigma^*\) such that \(ux\leftrightarrow^*_ Tvx?\) (2) Question: Does there exist a word \(x\in \Sigma^*\) such that \(xu\leftrightarrow^*_ Txv?\) It is shown that these problems are undecidable in general. In fact, they remain undecidable, even when they are restricted to presentations involving finite Church-Rosser Thue systems. On the other hand, when they are restricted to finite presentations involving monadic Church-Rosser Thue systems, then these two problems are decidable in polynomial space.