About the implementability and the power of equationally defined data abstractions

AbstractThe question of implementability and expressive power of equational axiom definitions of data abstractions is faced in the paper from the point of view of computability theory.A definition of implementable algebra is given, which looks reasonable and very general. With respect to the given definition it is proved that, if the least congruence semantics is accepted, an equationally defined data algebra is implementable if and only if the least congruence on terms induced by the equational definition is decidable. Moreover, the paper shows that there are: (a) equationally defined data algebras that cannot be implemented; (b) implementable algebras that cannot be expressed in any way by equational axioms