Skip to content

Research at St Andrews

Two variants of the froidure-pin algorithm for finite semigroups

Research output: Contribution to journalArticlepeer-review

DOI

Open Access permissions

Open

Abstract

In this paper, we present two algorithms based on the Froidure-Pin Algorithm for computing the structure of a finite semigroup from a generating set. As was the case with the original algorithm of Froidure and Pin, the algorithms presented here produce the left and right Cayley graphs, a confluent terminating rewriting system, and a reduced word of the rewriting system for every element of the semigroup. If U is any semigroup, and A is a subset of U, then we denote by <A> the least subsemigroup of U containing A. If B is any other subset of U, then, roughly speaking, the first algorithm we present describes how to use any information about <A>, that has been found using the Froidure-Pin Algorithm, to compute the semigroup <A∪B>. More precisely, we describe the data structure for a finite semigroup S given by Froidure and Pin, and how to obtain such a data structure for <A∪B> from that for <A>. The second algorithm is a lock-free concurrent version of the Froidure-Pin Algorithm.

Close

Details

Original languageEnglish
Pages (from-to)173-200
Number of pages28
JournalPortugaliae Mathematica
Volume74
Issue number3
DOIs
Publication statusPublished - 8 Feb 2018

    Research areas

  • Algorithms, Green's relations, Monoids, Semigroups

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. Bitangents of non-smooth tropical quartics

    Lee, H. & Len, Y., 5 Jul 2018, In: Portugaliae Mathematica. 75, 1, p. 67-78

    Research output: Contribution to journalArticlepeer-review

  2. Special issue on computational algebra

    Araújo, J. & Cameron, P. J., 9 Feb 2018, In: Portugaliae Mathematica. 74, 3, p. 171-172 2 p.

    Research output: Contribution to journalArticlepeer-review

  3. Synchronization and separation in the Johnson schemes

    Aljohani, M., Bamberg, J. & Cameron, P. J., 9 Feb 2018, In: Portugaliae Mathematica. 74, 3, p. 213-232

    Research output: Contribution to journalArticlepeer-review

ID: 249695343

Top