### Abstract

This paper studies decision problems for semigroups that are word-hyperbolic in the sense of Duncan and 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. (This does not alter the class of word-hyperbolic semigroups.) The isomorphism problem is proven to be undecidable for word-hyperbolic semigroups (in contrast to the situation for word-hyperbolic groups). It is proved that it is undecidable whether a word-hyperbolic semigroup is automatic, asynchronously automatic, biautomatic, or asynchronously biautomatic. (These properties do not hold in general for word-hyperbolic semigroups.) It is proved that the uniform word problem for word-hyperbolic semigroups is 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.

Original language | English |
---|---|

Pages (from-to) | 287-321 |

Number of pages | 35 |

Journal | Journal of Algebra |

Volume | 465 |

DOIs | |

Publication status | Published - 1 Nov 2016 |

### Fingerprint

### Keywords

- Context-free languages
- Decision problems
- Isomorphism problem
- Undecidability
- Word-hyperbolic semigroups

### Cite this

*Journal of Algebra*,

*465*, 287-321. https://doi.org/10.1016/j.jalgebra.2016.07.007