Algorithmic problems in varieties. (English) Zbl 0837.08002

This substantial paper presents a coherent picture of algorithmic problems in varieties of various types of algebras. Here the word problem plays the central rôle, but many others, such as the identity problem and the isomorphism problem are also considered. And central to all of this is the concept of a variety. Section two deals with general ideas of algorithmic problems in varieties, showing some surprising connections, such as: Connection 2.5: If every relatively free algebra in every subvariety of a variety \({\mathcal V}\) is residually finite, then the identity problem in \({\mathcal V}\) is solvable; and Connection 2.9: If all subvarieties of a variety \({\mathcal V}\) are finitely based, then the equational problem in the finite trace \({\mathcal V}_{\text{fin}}\) is soluble. Sections three to six deal with these problems in varieties of specific types of algebras, namely semigroups, associative algebras, Lie algebras and groups. The final section deals with methods of proving these results, in particular giving an exposition of the concept of Minsky machines. It is also shown that in the cases of groups and Lie and associative algebras, an even more powerful tool than a Minsky machine is a method of simulating differential equations. The whole paper contains over forty open problems as well as a number of conjectures, which should provide a great stimulus to workers in the field. The paper ends with 433 references. Although this is basically a survey, it does contain a number of results which have not appeared elsewhere, such as the following theorem (due to the second author): Theorem 3.22: The variety given by the identity \(x^3 = 0\) has the Higman property, that is, every semigroup from this variety which is given by a recursively enumerable set of defining relations is embeddable in a semigroup which is finitely presented in this variety. A paper of this length could well have been published as a monograph, and perhaps it should have been, since then it might have had an index, which would have added greatly to its readability.


08A50 Word problems (aspects of algebraic structures)
20E10 Quasivarieties and varieties of groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
17B01 Identities, free Lie (super)algebras
16R10 \(T\)-ideals, identities, varieties of associative rings and algebras
68W30 Symbolic computation and algebraic computation
20M07 Varieties and pseudovarieties of semigroups
20M05 Free semigroups, generators and relations, word problems
03D40 Word problems, etc. in computability and recursion theory
Full Text: DOI