×

Algorithmic problems in varieties of semigroups. (English. Russian original) Zbl 0683.20048

Algebra Logic 27, No. 4, 275-292 (1988); translation from Algebra Logika 27, No. 4, 440-463 (1988).
Let \({\mathcal M}\) be a finitely based nonperiodic variety of semigroups, then the following conditions are equivalent:
(1) All the finitely presented semigroups (f.p.s.) of \({\mathcal M}\) have solvable word problem.
(2) All the f.p.s. of \({\mathcal M}\) have solvable elementary theory.
(3) All the f.p.s. of \({\mathcal M}\) are finitely approximated.
(4) All the f.p.s. of \({\mathcal M}\) are imbeddable in matrix semigroups (over a field).
(5) \({\mathcal M}\) has identities of the form \(x^ ny(z^ kt^ k)^ pz^ m=x^ m(t^ kx^ k)^ pyz^ n\), \(xy^ nz=y^ kzy^ mzy^ p\), \(n>m.\)
(6) \({\mathcal M}=\{\bar P\times P^ 1\), \(\bar P^ 1\times P\), \(T\}\), where \(P=\{e_{11},e_{12},0\}\) \(T=\{e_{11},e_{12},e_{22},0\}\), \({}^- \) is an antiisomorphism, \(P^ 1=P\cup \{1\}.\)
Reviewer: L.A.Bokut’

MSC:

20M05 Free semigroups, generators and relations, word problems
20M07 Varieties and pseudovarieties of semigroups
08A50 Word problems (aspects of algebraic structures)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. A. Bokut’, ”Algorithmic problems and questions of embedding: some open questions for rings, groups, and semigroups,” Izv. Vyssh. Uchebn. Zaved., Mat., No. 11, 3–11 (1982). · Zbl 0513.17001
[2] R. M. Remeslennikov and V. A. Roman’kov, ”Model-theoretic and algorithmic questions in group theory,” in: Itogi Nauki i Tekhniki. Algebra. Topologiya. Geometriya,23, VINITI, Moscow (1982), pp. 3–79.
[3] S. I. Adyan and G. S. Makanin, ”Investigations in algorithmic questions of algebra,” in: Trudy Mat. Inst. Akad. Nauk SSSR, Vol. 168, Nauka, Moscow (1984), pp. 197–217. · Zbl 0549.20020
[4] A. I. Mal’tsev, ”On homomorphisms on finite groups,” Uch. Zap. Ivanovsk. Ped. Inst.,18, 49–60 (1958).
[5] M. A. Taitslin, ”Algorithmic problems for commutative semigroups,” Dokl. Akad. Nauk SSSR,178, No. 4, 786–789 (1968).
[6] L. Redei, Theorie der endlich erzeugbaren commutativen Halbgruppen (Hamburger Math. Einzelschriften41), Physica-Verlag, Würzburg (1963). · Zbl 0126.04205
[7] I. L. Mel’nichuk, ”Unsolvability of the problems of equality, divisibility in some varieties of semigroups,” Algebra Logika,23, No. 4, 430–438 (1984).
[8] I. L. Mel’nichuk, M. V. Sapir, and O. G. Kharlampovich, ”The equality problem in varieties of semigroups, rings and Lie algebras,” Sib. Mat. Zh.,27, No. 6, 144–156 (1986).
[9] A. Tarski, ”Equational logic and equational theories of algebras,” in: Contributions to Mathematical Logic, North-Holland, Amsterdam (1968), pp. 278–288. · Zbl 0209.01402
[10] M. V. Sapir, ”Problems of Burnside type and finite basedness in varieties of semigroups,” Izv. Akad. Nauk SSSR, Ser. Mat.,51, No. 2, 319–340 (1987).
[11] G. Lallement, Semigroups and Combinatorial Applications, Wiley, New York (1979). · Zbl 0421.20025
[12] M. V. Sapir, ”Algorithmic problems in varieties of semigroups,” Seventh All-Union Conference on Mathematical Logic, Novosibirsk (1984), pp. 160–161.
[13] A. I. Mal’tsev, ”On representations of infinite algebras,” Mat. Sb.,13, No. 2, 263–286 (1943). · Zbl 0060.07804
[14] H. Neumann, Varieties of Groups, Springer, Berlin (1967). · Zbl 0149.26704
[15] P. Perkins, ”Bases for equational theories of semigroups,” J. Algebra,11, No. 2, 293–314 (1969). · Zbl 0186.03401 · doi:10.1016/0021-8693(69)90058-1
[16] A. M. Slobodskoi, ”Unsolvability of the universal theory of finite groups,” Algebra Logika,20, No. 2, 207–230 (1981).
[17] L. A. Skornyakov, ”Characterization of a category of polygons,” Mat. Sb.,80, No. 4, 492–502 (1969). · Zbl 0203.31403
[18] A. I. Zimin, ”Semigroup varieties with finiteness conditions for finitely generated semigroups,” Dep. at VINITI, 27.10.1980, No. 4519-80.
[19] S. I. Kublanovskii, ”Locally residually finite and locally representable varieties of associative rings and algebras,” Dep. at VINITI, 14.12.1982, No. 6143-82.
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.