Skip to content

Research at St Andrews

Computing finite semigroups

Research output: Contribution to journalArticlepeer-review

Open Access permissions

Open

Author(s)

James East, Attila Egri-Nagy, James D. Mitchell, Yann Péresse

School/Research organisations

Abstract

Using a variant of Schreier's Theorem, and the theory of Green's relations, we show how to reduce the computation of an arbitrary subsemigroup of a finite regular semigroup to that of certain associated subgroups. Examples of semigroups to which these results apply include many important classes: transformation semigroups, partial permutation semigroups and inverse semigroups, partition monoids, matrix semigroups, and subsemigroups of finite regular Rees matrix and 0-matrix semigroups over groups. For any subsemigroup of such a semigroup, it is possible to, among other things, efficiently compute its size and Green's relations, test membership, factorize elements over the generators, find the semigroup generated by the given subsemigroup and any collection of additional elements, calculate the partial order of the D-classes, test regularity, and determine the idempotents. This is achieved by representing the given subsemigroup without exhaustively enumerating its elements. It is also possible to compute the Green's classes of an element of such a subsemigroup without determining the global structure of the semigroup.

Close

Details

Original languageEnglish
Pages (from-to)110-155
Number of pages46
JournalJournal of Symbolic Computation
Volume92
Early online date14 Feb 2018
DOIs
Publication statusPublished - May 2019

    Research areas

  • Semigroups, Monoids, Regular semigroups, Subsemigroups, Algorithms, Graphs, Digraphs, Green's relations

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

View graph of relations

Related by author

  1. GAP – Groups, Algorithms, and Programming, Version 4.11.1

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 2 Mar 2021

    Research output: Non-textual formSoftware

  2. Libsemigroups

    Mitchell, J. D., 28 May 2020

    Research output: Non-textual formSoftware

  3. Sets of universal sequences for the symmetric group and analogous semigroups

    Hyde, J., Jonušas, J., Mitchell, J. D. & Péresse, Y. H., May 2020, In: Proceedings of the American Mathematical Society. 148, 5, p. 1917-1931

    Research output: Contribution to journalArticlepeer-review

  4. GAP – Groups, Algorithms, and Programming, Version 4.11.0

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 29 Feb 2020

    Research output: Non-textual formSoftware

  5. GAP – Groups, Algorithms, and Programming, Version 4.10.2

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 19 Jun 2019

    Research output: Non-textual formSoftware

Related by journal

  1. Lifting tropical bitangents

    Len, Y. & Markwig, H., Jan 2020, In: Journal of Symbolic Computation. 96, p. 122-152

    Research output: Contribution to journalArticlepeer-review

  2. Polynomial-time proofs that groups are hyperbolic

    Holt, D., Linton, S., Neunhoeffer, M., Parker, R., Pfeiffer, M. & Roney-Dougal, C. M., May 2021, In: Journal of Symbolic Computation. 104, p. 419-475

    Research output: Contribution to journalArticlepeer-review

  3. New refiners for permutation group search

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

    Research output: Contribution to journalArticlepeer-review

  4. Integrality and arithmeticity of solvable linear groups

    Detinko, A., Flannery, D. & de Graaf, W., 2015, In: Journal of Symbolic Computation. 68, p. 138–145

    Research output: Contribution to journalArticlepeer-review

ID: 242971941

Top