×

Computing transformation semigroups. (English) Zbl 1002.20043

The paper describes data structures and algorithms for performing computations in a finite semigroup \(S\) with identity, generated by a set of transformations. A basic idea behind the algorithms is the partition of \(S\) with the aid of an equivalence relation \(\mathcal R\), one of Green’s relations. The paper presents algorithms for performing global computations in \(S\) (like its size and structure), as well as local computations within an \(\mathcal R\)-class, without touching the rest of \(S\), thereby improving existing results by G. Lallement and R. McFadden [J. Symb. Comput. 10, No. 5, 481-498 (1990; Zbl 0792.20061)]. This approach is bound to result in more efficient computations.
The algorithms have been implemented in the GAP computer algebra system, and are available as the share package MONOID. Examples of computations using MONOID are given in the paper.

MSC:

20M20 Semigroups of transformations, relations, partitions, etc.
68W30 Symbolic computation and algebraic computation
20M10 General structure theory for semigroups
20M30 Representation of semigroups; actions of semigroups on sets

Citations:

Zbl 0792.20061

Software:

GAP; MONOiD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0207.01701
[2] J. J. Cannon, 1969; J. J. Cannon, 1969
[3] Howie, J. M., Fundamentals of Semigroup Theory (1995), Oxford University Press: Oxford University Press Oxford · Zbl 0835.20077
[4] Lallement, G.; McFadden, R., On the determination of Green’s relations in finite transformation semigroups, J. Symb. Comput., 10, 481-489 (1990) · Zbl 0792.20061
[5] Linton, S. A.; Pfeiffer, G.; Robertson, E. F.; Ruškuc, N., Groups and actions in transformation semigroups, Math. Z., 228, 435-450 (1998) · Zbl 0902.20028
[6] S. A. Linton, G. Pfeiffer, E. F. Robertson, N. Ruškuc, \(MONOID, GAP\); S. A. Linton, G. Pfeiffer, E. F. Robertson, N. Ruškuc, \(MONOID, GAP\)
[7] Luks, E. M., Permutation groups and polynomial-time computation, (Finkelstein, L.; Kantor, W. M., number 11 in Groups and Computation (1993), American Mathematical Society: American Mathematical Society Providence, RI), 139-175 · Zbl 0813.20004
[8] Schönert, M., \(GAP\)—Groups, Algorithms, and Programming (1995), Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule. Germany, Aachen See http://www-gap.dcs.st-and.ac.uk/ gap.
[9] Sims, C. C., Computational methods in the study of permutation groups, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) (1970), Pergamon: Pergamon Oxford, p. 169-183 · Zbl 0215.10002
[10] C. C. Sims, Proceedings of \(2^{ nd }\) Symposium on Symbolic and Algebraic Manipulation, Petrick, S. R. 1971, ACM, New York, 23, 28; C. C. Sims, Proceedings of \(2^{ nd }\) Symposium on Symbolic and Algebraic Manipulation, Petrick, S. R. 1971, ACM, New York, 23, 28
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.