×

Algorithms for computing finite semigroups. (English) Zbl 0876.20034

Cucker, Felipe (ed.) et al., Foundations of computational mathematics. Selected papers of a conference, held at IMPA in Rio de Janeiro, Brazil, January 1997. Berlin: Springer. 112-126 (1997).
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].

MSC:

20M05 Free semigroups, generators and relations, word problems
68W30 Symbolic computation and algebraic computation

Software:

Semigroupe
PDFBibTeX XMLCite
Full Text: DOI