[FOM] more about identities

[A. Mani]

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.

Best

A. Mani
Member, Cal. Math. Soc






 
> Martin
>
>
>                            Martin Davis
>                     Visiting Scholar UC Berkeley
>                       Professor Emeritus, NYU
>                           martin at eipye.com
>                           (Add 1 and get 0)
>                         http://www.eipye.com
>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom