Nondeterminism has been useful as a high-level expression of parallelism, as in pure logic programming, and in control structures that avoid explicit choices between different but acceptable alternatives, as in Dijkstra’s if-fi. Similarly, nondeterminism may be useful in expressing data types that avoid specification of one concrete representation among many that are acceptable. Unfortunately, a theory of nondeterministic data types is somewhat tedious for operations that result in Cartesian products and that involve coupling of nondeterministic choices on components of products. This paper develops such a theory using a generalization of term algebras. The generalization is based on a rather involved extension of arrows of signatures, which the author calls accumulated arrows. This extension is the tedious part of the generalization of term algebras, but Hesselink feels that it may have general utility in deterministic as well as nondeterministic data types.

Using input/output behavior as an intuitive basis, definitions of implementation and implementation equivalence of nondeterministic data types are given, providing a correctness criterion for implementations. Examples are given, and one example shows that implementation-equivalent models may have different input/output behavior. This seems strange, but perhaps it is only the case with a fairness assumption of the type used in the example. In any event, the point needs clarification.

Using his theory of nondeterministic data types, the author defines variations of extraction equivalence of values, observable equivalence of values, and two other equivalence relations of interest for nondeterministic types. These four notions are equivalent for deterministic data types but are distinct in the nondeterministic case, as is shown by a thorough comparison.

In general, the paper is quite sound and evokes interest in applying nondeterministic data types. However, applications that are more convincingly useful than those given in the paper are needed.