‘Decision problems for word-hyperbolic semigroups’
[with M. Pfeiffer]
Journal of Algebra, 465 (November 2016), pp. 287–321.
DOI: 10.1016/j.jalgebra.2016.07.007.

Abstract

This paper studies decision problems for semigroups that are word-hyperbolic in the sense of Duncan & Gilman. A fundamental investigation reveals that the natural definition of a ‘word-hyperbolic structure’ has to be strengthened slightly in order to define a unique semigroup up to isomorphism. It is proved that every word-hyperbolic semigroup has word problem solvable in polynomial time (improving on the previous exponential-time algorithm). Algorithms are presented for deciding whether a word-hyperbolic semigroup is a monoid, a group, a completely simple semigroup, a Clifford semigroup, or a free semigroup.