Data type specification
J. W. Thatcher, Eric G. Wagner, Jesse B. Wright · ACM Symposium on Theory of Computing (STOC) · 1978
This paper extends our earlier work on abstract data types by providing an algebraic treatment of parametrized data types (e.g., sets-of-(), stacks-of-(), etc.), as well as answering a number of questions on the power and limitations of algebraic specification techniques. In brief: we investigate the “hidden function” problem (the need to include operations in specifications which we want to be hidden from the user); we prove that conditional specifications are inherently more powerful than equational specifications; we show that parameterized specifications must contain “side conditions” (e.g., that finite-sets-of-d requires an equality predicate on d), and we compare the power of the algebraic approach taken here with the more categorical approach of Lehman and Smyth.
Cited by 136 works. doi:10.1145/800133.804340 Open-access PDF
Authors
References
- Proof of correctness of data representations
- Computation: Finite and Infinite Machines.
- The mathematical theory of context free languages
- The mathematical theory of context-free languages
- Fundamentals of data structures
- Initial Algebra Semantics and Continuous Algebras
- Abstract data types and software validation
- Putting theories together to make specifications
- Fundamentals of data-structures
- The specification and application to programming of abstract data types.