×

Stable pairs. (English) Zbl 1209.20051

If \(V\) is a semigroup and \(v\in V\), the right stabilizer \(\mathrm{Stab}(v)\) of \(v\) is the set \(\{v'\mid vv'=v\}\). Given a finite semigroup \(S\) and a semigroup pseudovariety \(\mathbf V\), a pair \((Y,T)\), in which \(Y\) is a subset of \(S\) and \(T\) is a subsemigroup of \(S\), is called a \(\mathbf V\)-stable pair if for any relational morphism \(R\colon S\rightsquigarrow V\) with \(V\in\mathbf V\) there exists a \(v\in V\) such that \(Y\subseteq R^{-1}(v)\) and \(T\subseteq R^{-1}(\mathrm{Stab}(v))\). One says that \(\mathbf V\) has computable stable pairs if, given a finite semigroup \(S\) and a pair \((Y,T)\), in which \(Y\) is a subset of \(S\) and \(T\) is a subsemigroup of \(S\), one can decide whether or not \((Y,T)\) is \(\mathbf V\)-stable. It is known that if \(\mathbf W\) is a local pseudovariety of semigroups [in the sense of B. Tilson, J. Pure Appl. Algebra 48, 83-198 (1987; Zbl 0627.20031)] with decidable membership, and \(\mathbf V\)-stable pairs are computable, then the semidirect product \(\mathbf W*\mathbf V\) has decidable membership.
The author gives a description of \(\mathbf A\)-stable pairs where \(\mathbf A\) stands for the pseudovariety of all finite aperiodic semigroups (Theorem 1.10). This description, together with an earlier result by the author [J. Pure Appl. Algebra 55, No. 1-2, 85-126 (1988; Zbl 0682.20044)], implies that \(\mathbf A\)-stable pairs are computable. Thus, if \(\mathbf W\) is a local pseudovariety with decidable membership, then the semidirect product \(\mathbf W*\mathbf A\) has decidable membership (Corollary 1.11).

MSC:

20M07 Varieties and pseudovarieties of semigroups
20M05 Free semigroups, generators and relations, word problems
20M10 General structure theory for semigroups
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1142/S0218196799000163 · Zbl 1028.20038 · doi:10.1142/S0218196799000163
[2] DOI: 10.1142/S0218196791000079 · Zbl 0722.20039 · doi:10.1142/S0218196791000079
[3] DOI: 10.1090/S0002-9939-03-06860-6 · Zbl 1027.20035 · doi:10.1090/S0002-9939-03-06860-6
[4] DOI: 10.1016/0022-4049(88)90042-4 · Zbl 0682.20044 · doi:10.1016/0022-4049(88)90042-4
[5] K. Henckell, Semigroups. Algebraic Theory and Applications to Formal Languages and Codes, eds. C. Bonzini, A. Cherubini and C. Tibiletti (World Scientific, 1992) pp. 94–102.
[6] DOI: 10.1016/0022-4049(94)00055-N · Zbl 0836.20082 · doi:10.1016/0022-4049(94)00055-N
[7] DOI: 10.1007/978-1-4612-1388-8_6 · doi:10.1007/978-1-4612-1388-8_6
[8] DOI: 10.1142/S0218196704002006 · Zbl 1080.20054 · doi:10.1142/S0218196704002006
[9] DOI: 10.1007/BF02572755 · Zbl 0503.20028 · doi:10.1007/BF02572755
[10] S. M. Margolis, Kernels and Expansions: An Historical and Technical Perspective, Monoids and Semigroups with Applications, ed. J. Rhodes (1991) pp. 3–30. · Zbl 0826.20055
[11] DOI: 10.1142/S021819679900028X · Zbl 1027.20039 · doi:10.1142/S021819679900028X
[12] DOI: 10.1007/PL00020979 · doi:10.1007/PL00020979
[13] DOI: 10.1142/S021819670300150X · Zbl 1054.18001 · doi:10.1142/S021819670300150X
[14] DOI: 10.1006/aama.1997.0547 · Zbl 0879.68074 · doi:10.1006/aama.1997.0547
[15] DOI: 10.1016/0022-4049(87)90108-3 · Zbl 0627.20031 · doi:10.1016/0022-4049(87)90108-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.