[FOM] more about identities
a_mani_sc_gs at yahoo.co.in
Tue Feb 6 12:24:25 EST 2007
On Tuesday 06 Feb 2007 03:45, Martin Davis wrote:
> Thanks to all who replied to my inquiry about identities.
> It turns out that my friend is asking a more difficult question. He
> asks whether there is an algorithm to determine whether a given
> equation follows from a given finite set of such equations if THE
> OPERATIONS ARE RESTRICTED TO A SINGLE BINARY OPERATION. Constants and
> unary operations are not permitted.
This is exactly the identity problem for groupoids ( and above).
The word problem may be written in a similar way with relations as opposed to
identities and is quite different.
The undecidability of the identity problem for the class of finite semigroups
was proved by Albert et. al JSL 57(1) 1992
Murskii proved that for the class of all semigroups in Mat Zametki 1967-68.
For the variety of all algebras over a finite language, we have the uniformly
decidable word problem (1951).
Generally of course we have both positive and negative results for the problem
from the viewpoint of equational theories of algebras (semigroups,
groupoids). I do not know about a survey for groupoids on the problem. There
are some results by Jezek that relate to the problem though.
Member, Cal. Math. Soc
> Martin Davis
> Visiting Scholar UC Berkeley
> Professor Emeritus, NYU
> martin at eipye.com
> (Add 1 and get 0)
> FOM mailing list
> FOM at cs.nyu.edu
More information about the FOM