Decidability and tameness in the theory of finite semigroups.
type: Item
instance of: scholarly article
title: Decidability and tameness in the theory of finite semigroups.
zbMATH Open document ID: 1160.20056
author: Jorge Almeida
published in: Bulletin of the Iranian Mathematical Society
publication date: 2008-10-20T00:00:00Z
review text: 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.
reviewed by: K. Auinger
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 5354259
zbMATH Keywords: pseudovarieties of semigroups
zbMATH Keywords: varieties of finite semigroups
zbMATH Keywords: decidability of membership
zbMATH Keywords: tameness
zbMATH Keywords: Mal'tsev products
zbMATH Keywords: semidirect products
zbMATH Keywords: profinite semigroups
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5354259