Froidure, Véronique; Pin, Jean-Eric 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]. Reviewer: Y.Kobayashi (Funabashi) Cited in 1 ReviewCited in 14 Documents MSC: 20M05 Free semigroups, generators and relations, word problems 68W30 Symbolic computation and algebraic computation Keywords:algorithms; finite subsemigroups; reduced elements; Green relations Software:Semigroupe PDFBibTeX XMLCite \textit{V. Froidure} and \textit{J.-E. Pin}, in: Foundations of computational mathematics. Selected papers of a conference, held at IMPA in Rio de Janeiro, Brazil, January 1997. Berlin: Springer. 112--126 (1997; Zbl 0876.20034) Full Text: DOI