Decidability and tameness in the theory of finite semigroups. (Q949087)

This is a survey on the modern theory of pseudovarieties of finite semigroups with emphasis on the decidability of the membership problem. At the beginning, some historical remarks concerning connections with automata and formal language theory are presented (Schützenberger's theorem on star-free languages, Simon's theorem on piecewise testable languages, Eilenberg's variety theorem, the Krohn-Rhodes theorem), and, motivated by these results, operations on the lattice of pseudovarieties of finite semigroups (or monoids) are introduced (Mal'cev product, semidirect product, power, etc.). The main body of the text is devoted to profinite methods: after having defined the basic notions like (relatively) free profinite monoid, pseudo-identity, etc., Reiterman's theorem is stated and examples are given. Motivated by the membership problem in semidirect products \(\mathbf V*\mathbf W\), pseudovarieties of categories are introduced and two versions of a ``basis theorem'' for \(\mathbf V*\mathbf W\) are given. In the rest of the survey, tameness of pseudovarieties, computing closures of rational languages and connections with model theory are explored. Reviewer's remark: In section 4, it is claimed that the globals \(g\mathbf C_n\) of the complexity pseudovarieties \(\mathbf C_n=\mathbf A*(\mathbf G*\mathbf A)^n\) have infinite vertex rank and the result is attributed to \textit{J.~Rhodes} and \textit{B.~Steinberg}, [Int.~J.~Algebra Comput. 16, No. 4, 739-748 (2006; Zbl 1105.20049)]. However, that result is not stated in the cited paper, and, to the reviewer's knowledge, it is an open problem whether the globals of the complexity pseudovarieties have infinite vertex rank.