Nondeterminism in Data Types, a Mathematical Approach

摘要

The theory of abstract data types is generalized to the case of nondeterministic operations (set-valued functions). Since the nondeterminism of operations may be coupled, signatures are extended so that operations can have results in cartesian products. Input-output behavior is used to characterize implementation of one model by another. It is described by accumulated arrows, which form a variation of the term algebra. Morphisms of nondeterministic models are introduced. Both innovations prove to be powerful tools in the analysis of input-output behavior. Extraction equivalence and observable equivalence of values are investigated. Quotient models for equivalence relations are constructed. The equivalence relations are compared with each other, with separation of values, and with the separation property that characterizes a terminal model. Examples show that the four concepts are different. In deterministic models the concepts coincide.