×

zbMATH — the first resource for mathematics

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
Software:
GAP; MONOiD
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V; Hopcroft, J.E; Ullman, J.D, The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0207.01701
[2] J. J. Cannon, 1969
[3] Howie, J.M, Fundamentals of semigroup theory, (1995), 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\)
[7] Luks, E.M, Permutation groups and polynomial-time computation, (), 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 Oxford, p. 169-183 · Zbl 0215.10002
[10] C. C. Sims, Proceedings of 2^ndSymposium 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.