Abstract
We conceive a parametrized data type as a partial functor ϕ: ALG (σ) → ALG (δ), where δ is a signature extending σ and ALG (σ) is the class of minimal σ-algebras which serve as parameters.
We focus attention on one particular method of algebraically specifying parametrized data types: finite specifications with conditional equations using auxiliary sorts and functions provided with initial algebra semantics.
We introduce the concept of an effective parametrized data type. A satisfactory adequacy result is then obtained: each effective parametrized data type possesses a finite algebraic specification under initial semantics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
BERGSTRA, J.A. & J.W. KLOP, Algebraic specifications for parametrized data types with minimal parameter and target algebras, Mathematical. Centre, Department of Computer Science Research Report IW 183, Amsterdam 1981.
BERGSTRA, J.A. & J.W. KLOP, Initial algebra specifications for parametrized data types, Mathematical Centre, Department of Computer Science Research Report IW 186, Amsterdam 1981.
BERGSTRA, J.A. & J.V. TUCKER, Algebraic specifications of computable and semi-computable data structures, Mathematical Centre, Department of Computer Science Research Report IW 115, Amsterdam 1979.
BERGSTRA, J.A. & J.V. TUCKER, A characterization of computable data types by means of a finite equational specification method, Proc. 7th ICALP, Springer LNCS Vol. 85, 1980.
BERGSTRA, J.A. & J.V. TUCKER, Initial and final algebra semantics for data type specifications: two characterization theorems, Mathematical Centre, Department of Computer Science Research Report IW 131, Amsterdam 1980.
BURSTALL, R.M. & J.A. GOGUEN, An informal introduction to specifications using CLEAR, Lecture notes for the International Summer School on theoretical foundations of programming methodology, Munich 1981.
EHRICH, H.D., On the theory of specification, implementation and parametrization of abstract data types. Research Report Dortmund 1978.
EHRIG, H.E., H.-J. KREOWSKI, J.W. THATCHER, E.G. WAGNER & J.B. WRIGHT, Parameterized data types in algebraic specification languages, Proc. 7th ICALP, Springer LNCS Vol. 85, 1980.
EHRIG, H., Algebraic theory of parameterized specifications with requirements, in Proc. of CAAP81, Springer LNCS, Vol. 112.
GANZINGER, H., Parameterized specifications: parameter passing and optimizing implementation. Report TUM-18110. Technische UniversitÄt München, August 1981.
KAPHENGST, H. & H. REICHEL, Algebraische Algorithmentheorie, VEB Robotron, Dresden WIB, 1971.
LEHMANN, D.J. & M.B. SMYTH, Data types, Proc. 18th IEEE Symposium on Foundations of Computing, Providence R.I. November 1977.
Rogers jr., H., Theory of recursive functions and effective computability, McGraw-Hill, 1967.
Scott, D.S., Lambda calculus and recursion theory, in Proc. Third Scandinavian Logic Conf., Ed. S. Kanger, North Holland Studies in Logic and the Foundations of Mathematics, Vol. 82, 1975.
Thatcher, J.W., E.G. Wagner & J.B. Wright, Data type specification: parameterization and the power of specification techniques, Proc. SIGACT 10th Annual Symp. on Theory of Computing, pp. 119–132, May 1978.
Wirsing, M., An analysis of semantic models for algebraic specifications, Lecture Notes for the International Summer School on theoretical foundations of programming methodology, Munich 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1982 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bergstra, J.A., Klop, J.W. (1982). Algebraic specifications for parametrized data types with minimal parameter and target algebras. In: Nielsen, M., Schmidt, E.M. (eds) Automata, Languages and Programming. ICALP 1982. Lecture Notes in Computer Science, vol 140. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0012754
Download citation
DOI: https://doi.org/10.1007/BFb0012754
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-11576-2
Online ISBN: 978-3-540-39308-5
eBook Packages: Springer Book Archive