A mathematical approach to nondeterminism in data types

ABSTRACT

The theory of abstract data types is generalized to the case of nondeterministic operations (set-valuedfunctions). 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 means of accumulated arrows, which form a generalization 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 such equivalence relations are constructed. The equivalence relations are compared with each other, with separation of values by means of experiments, and with the separation property that characterizes a terminal model. Examples are given to show that the four concepts are different. In deterministic models the concepts coincide.

REFERENCES

• 1: BERGSTRA, J. A., AND KLOP, J. W. Algebra of communicating processes. In Proceedings of the CWZ Symposium on Mathematics and Computer Science (Amsterdam, Oct. 6-7,1986). Centre for Mathematics and Computer Science, Amsterdam, 1986, pp. 89-138.
• 2: BERZTISS, A. T., AND THA~E, S. Specification and implementation of abstract data types. In Advances in Computers, vol. 22. M. C. Yovits, Ed. Academic Press, New York, 1983, pp. 295-353.
• 3: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 4: Joseph A. Goguen , José Meseguer, Universal Realization, Persistent Interconnection and Implementation of Abstract Modules, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.265-281, July 12-16, 1982
• 5: GUTTAG, J. V., AND HORNING, J. J. The algebraic specification of abstract data types. In Programming Methodology, D. Gries, Ed. Springer-Verlag, New York, pp. 282-308.
• 6: HANSOUL, G. E. A subdirect decomposition theorem for multialgebras. Algebra universalis 16 (1983), 275-281.
• 7: HESSELINK, W. H. A theory of non-deterministic data structures. Computing Science Notes, Rep. CS 8503, Dept. of Mathematics and Computer Science, Groningen State Univ., Groningen, 1985.
• 8: JONES, C. B. Development methods for computer programs including a notion of interference. Ph.D. dissertation, Rep. PRG 25, Oxford Univ., 1981.
• 9: Samuel Kamin, Final Data Types and Their Specification, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.97-121, Jan. 1983 [doi>10.1145/357195.357202]
• 10: D. Kapur, TOWARDS A THEORY FOR ABSTRACT DATA TYPES, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 11: MACLANE, S. Categories for the Working Mathematician. Springer-Verlag, New York, 1971.
• 12: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 13: PICKETT H. E. Homomorphisms and subalgebras of multislgebras. Pac. J. Math. 212, (1967), 327-342.
• 14: Donald Sannella , Martin Wirsing, A Kernel Language for Algebraic Specification and Implementation - Extended Abstract, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.413-427, August 21-27, 1983
• 15: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 16: P. A. Subrahmanyam, Nondeterminism in Abstract Data Types, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.148-164, July 13-17, 1981
• 17: WIRSING, M., PEPPER, P., PARTSCH, H., DOSCH, W., AND BROY, M. On hierarchies of abstract data types. Acta In/I 20 (1983), l-33.
• 18: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Design, Languages, Theory