Decidability and tameness in the theory of finite semigroups.
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.
- Some key problems on finite semigroups
- Finite semigroup varieties of the form V*D
- Globals of pseudovarieties of commutative semigroups: the finite basis problem, decidability and gaps
- On the decidability of membership in the global of a monoid pseudovariety.
- scientific article; zbMATH DE number 4008680 (Why is no real title available?)
- Irreducibility of certain pseudovarieties1
- scientific article; zbMATH DE number 1944113 (Why is no real title available?)
- UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
- Decidability of the representation extension property for finite semigroups
- A delay theorem for pointlikes
- Semidirect product with an order-computable pseudovariety and tameness.
- Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring
This page was built for publication: Decidability and tameness in the theory of finite semigroups.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q949087)
