NON-DETERMINISTIC HYPERIDENTITIES IN MANY-SORTED ALGEBRAS

Abstract

Many-sorted algebras are used in Computer Science for abstract data type specifications. It is widely believed that many-sorted algebras are the appropriate mathematical tools to explain what abstract data types are ([6]). In this paper we extend the approach to non-deterministic hypersubstitutions and non-deterministic hyperidentities given in [4] to the many-sorted case. The main result is the characterization of non- deterministic solid varieties. This will be done by showing that on the basis of non-deterministic hypersubstitutions one obtains a conjugate pair of additive closure operators which allows to apply the theory of conjugate pairs of additive closure operators also to this case (see [7]). Our results form a universal-algebraic background of the theory of many- sorted tree languages (see [8]).