Computing finite semigroups
From MaRDI portal
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 -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 -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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3841211 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 3608316 (Why is no real title available?)
- scientific article; zbMATH DE number 1226898 (Why is no real title available?)
- scientific article; zbMATH DE number 3436618 (Why is no real title available?)
- scientific article; zbMATH DE number 951516 (Why is no real title available?)
- scientific article; zbMATH DE number 1849958 (Why is no real title available?)
- scientific article; zbMATH DE number 789816 (Why is no real title available?)
- scientific article; zbMATH DE number 3341276 (Why is no real title available?)
- scientific article; zbMATH DE number 3047078 (Why is no real title available?)
- AUTOMATE, a computing package for automata and finite semigroups
- Algorithms for computing finite semigroups
- Cellularity of diagram algebras as twisted semigroup algebras.
- Computers in semigroups
- Computing automorphisms of semigroups.
- Computing the ideal structure of finite semigroups
- Computing the maximum generalized inverse of a Boolean matrix
- Computing transformation semigroups
- Depth-First Search and Linear Graph Algorithms
- Diagram monoids and Graham-Houghton graphs: idempotents and generating sets of ideals
- Generating Sets of Completely 0-Simple Semigroups
- Green's equivalences in finite semigroups of binary relations
- Groups and actions in transformation semigroups
- Membership testing in commutative transformation semigroups
- ON THE PARTITION MONOID AND SOME RELATED SEMIGROUPS
- On the determination of Green's relations in finite transformation semigroups
- Path-based depth-first search for strong and biconnected components
- Recursive unsolvability of a problem of Thue
- Regular * semigroups
- Regular elements of the semigroup of all binary relations
- SWAC Computes 126 Distinct Semigroups of Order 4
- The Magma algebra system. I: The user language
- The \(\mathfrak q\)-theory of finite semigroups.
- The computational matrix group project.
Cited in
(17)- Green index in semigroups: generators, presentations, and automatic structures.
- The complexity of properties of transformation semigroups
- Polynomial time multiplication and normal forms in free bands
- Computing denumerants in numerical 3-semigroups
- Enumeration of idempotents in planar diagram monoids
- Random ubiquitous transformation semigroups
- Computing finite commutative semigroups. II.
- Computing transformation semigroups
- Green's relations in finite transformation semigroups
- Enumeration of finite inverse semigroups
- Computing maximal subsemigroups of a finite semigroup
- Computing character tables and Cartan matrices of finite monoids with fixed point counting
- Effective dimension of finite semigroups.
- Two variants of the Froidure-Pin algorithm for finite semigroups
- Minimum degrees of finite rectangular bands, null semigroups, and variants of full transformation semigroups
- Digital representation of semigroups and groups
- Computing with semigroups in GAP. -- A tutorial
Describes a project that uses
Uses Software
This page was built for publication: Computing finite semigroups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1757008)
