Articles

‘Cancellativity is undecidable for automatic semigroups’

Quarterly Journal of Mathematics 57 (2006), no. 3, pp. 285–295.
doi: 10.1093/qmath/hai023. MR: 2253587. $ZBL1126.20039
[ Download preprint ]

Abstract

Via an encoding of the Modified Post’s Correspondence Problem, this paper shows that it is undecidable whether an automatic semigroup is cancellative.

[ See also: ‘A note on “Cancellativity is undecidable for automatic semigroups”’ ]