Skip to content

Research at St Andrews

Decision problems for word-hyperbolic semigroups

Research output: Contribution to journalArticle

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. 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 semigroup 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.
Close

Details

Original languageEnglish
Pages (from-to)287-321
JournalJournal of Algebra
Volume465
Early online date22 Jul 2016
DOIs
StatePublished - 1 Nov 2016

    Research areas

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

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. New refiners for permutation group search

    Jefferson, C., Pfeiffer, M. & Waldecker, R. 11 Jan 2018 In : Journal of Symbolic Computation. 92, p. 70-92 23 p.

    Research output: Contribution to journalArticle

  2. Minimal and canonical images

    Jefferson, C., Jonauskyte, E., Pfeiffer, M. & Waldecker, R. 22 Nov 2018 In : Journal of Algebra. In press

    Research output: Contribution to journalArticle

  3. Two variants of the froidure-pin algorithm for finite semigroups

    Jonusas, J., Mitchell, J. D. & Pfeiffer, M. 8 Feb 2018 In : Portugaliae Mathematica. 74, 3, p. 173-200 28 p.

    Research output: Contribution to journalArticle

  4. Francy - an interactive discrete mathematics framework for GAP

    Martins, M. M. & Pfeiffer, M. J. 2018 Mathematical Software – ICMS 2018: 6th International Conference, South Bend, IN, USA, July 24-27, 2018, Proceedings. Davenport, J. H., Kauers, M., Labahn, G. & Urban, J. (eds.). Cham: Springer, p. 352-358 (Lecture Notes in Computer Science (Theoretical Computer Science and General Issues); vol. 10931)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  5. Finite presentability and isomorphism of Cayley graphs of monoids

    Awang, J. S., Pfeiffer, M. J. & Ruskuc, N. Nov 2017 In : Proceedings of the American Mathematical Society. 145, 11, p. 4585-4593

    Research output: Contribution to journalArticle

Related by journal

  1. Computing maximal subsemigroups of a finite semigroup

    Donoven, C. R., Mitchell, J. D. & Wilson, W. A. 1 Jul 2018 In : Journal of Algebra. 505, p. 559-596 38 p.

    Research output: Contribution to journalArticle

  2. Enumeration of idempotents in planar diagram monoids

    Dolinka, I., East, J., Evangelou, A., FitzGerald, D., Ham, N., Hyde, J., Loughlin, N. & Mitchell, J. D. 26 Nov 2018 In : Journal of Algebra. In press

    Research output: Contribution to journalArticle

  3. Finiteness properties of direct products of algebraic structures

    Mayr, P. & Ruskuc, N. 15 Jan 2018 In : Journal of Algebra. 494, p. 167-187

    Research output: Contribution to journalArticle

  4. Maximal subsemigroups of finite transformation and diagram monoids

    East, J., Kumar, J., Mitchell, J. D. & Wilson, W. A. 15 Jun 2018 In : Journal of Algebra. 504, p. 176-216

    Research output: Contribution to journalArticle

  5. Minimal and canonical images

    Jefferson, C., Jonauskyte, E., Pfeiffer, M. & Waldecker, R. 22 Nov 2018 In : Journal of Algebra. In press

    Research output: Contribution to journalArticle

ID: 191070636