Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao zbMATH Openarrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
International Journal of Algebra and Computation
Article . 1995 . Peer-reviewed
Data sources: Crossref
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

ALGORITHMIC PROBLEMS IN VARIETIES

Algorithmic problems in varieties
Authors: Kharlampovich, O. G.; Sapir, M. V.;

ALGORITHMIC PROBLEMS IN VARIETIES

Abstract

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.

Keywords

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

  • BIP!
    Impact byBIP!
    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%
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
94
Top 10%
Top 1%
Top 10%
Related to Research communities
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!