
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.
equational problem, Free semigroups, generators and relations, word problems, isomorphism problem, groups, open problems, Symbolic computation and algebraic computation, identity problem, semigroups, Quasivarieties and varieties of groups, relatively free algebra, Higman property, Lie algebras, varieties of algebras, survey, Word problems, etc. in computability and recursion theory, word problem, \(T\)-ideals, identities, varieties of associative rings and algebras, Identities, free Lie (super)algebras, Minsky machines, simulating differential equations, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), Varieties and pseudovarieties of semigroups, algorithmic problems, Word problems (aspects of algebraic structures), associative algebras
equational problem, Free semigroups, generators and relations, word problems, isomorphism problem, groups, open problems, Symbolic computation and algebraic computation, identity problem, semigroups, Quasivarieties and varieties of groups, relatively free algebra, Higman property, Lie algebras, varieties of algebras, survey, Word problems, etc. in computability and recursion theory, word problem, \(T\)-ideals, identities, varieties of associative rings and algebras, Identities, free Lie (super)algebras, Minsky machines, simulating differential equations, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), Varieties and pseudovarieties of semigroups, algorithmic problems, Word problems (aspects of algebraic structures), associative algebras
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 94 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
