Algorithms for computing finite semigroups (Q4336094)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1008355
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Algorithms for computing finite semigroups |
scientific article; zbMATH DE number 1008355 |
Statements
Algorithms for computing finite semigroups (English)
0 references
24 November 1997
0 references
algorithms
0 references
finite subsemigroups
0 references
reduced elements
0 references
Green relations
0 references
0.8587343096733093
0 references
0.8547926545143127
0 references
0.8434379696846008
0 references
0.8077552914619446
0 references
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].
0 references