Cancellativity in finitely presented semigroups (Q1824041): Difference between revisions

This paper considers whether or not cancellativity is decidable in finitely presented semigroups answering questions raised in a paper by \textit{R. Book} [J. Symb. Comput. 3, 39-68 (1987; Zbl 0638.68091)]. Cancellativity is shown to be undecidable in semigroups presented by Thue systems even if the systems are monadic. In general, cancellativity is even undecidable in semigroups presented by Church-Rosser Thue systems, but decidable if the system is monadic. For semigroups which are presented by commutative Thue systems cancellativity is decidable; the negation is in NP if the system is canonical.