Algorithms for computing finite semigroups

From MaRDI portal





The authors give a simple algorithm which computes the finite subsemigroup \(M\) generated by a given set \(A\) in a large semigroup \(U\) called the universe. The algorithm constructs a complete list of reduced elements of \(M\) and rewrite rules for \(M\). The list is initialized as the singleton with the empty word. For each element \(u\) of the list being computed and for \(a\in A\), it computes \(u\cdot a\) in \(U\). If its value \(v\) already exists in the list, it produces the rule \(ua\to v\). Otherwise it adds the new element \(v\) to the list. They also give an improved version of the algorithm and apply it to compute the Green relations etc. For the entire collection see [Zbl 0857.00037].




Cited in
(35)


Describes a project that uses

Uses Software






This page was built for publication: Algorithms for computing finite semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4336094)