Initial and Final Algebra Semantics for Data Type Specifications: Two Characterization Theorems
Authors:
- J. A. BergstraJBJ. A. Bergstra
- J. V. TuckerJTJ. V. Tucker
- 1 May 1983
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 12 (2) , 366-387
Abstract
We prove that those data types which may be defined by conditional equation specifications and final algebra semantics are exactly the cosemicomputable data types-those data types which are effectively computable, but whose inequality relations are recursively enumerable. And we characterize the computable data types as those data types which may be specified by conditional equation specifications using both initial algebra semantics and final algebra semantics. Numerical bounds for the number of auxiliary functions and conditional equations required are included in both theorems.Keywords
This publication has 12 references indexed in Scilit:
- Terminal algebra semantics and retractions for abstract data typesLecture Notes in Computer Science, 1980
- A characterisation of computable data types by means of a finite equational specification method1980
- On the adequacy of finite equational methods for data type specificationACM SIGPLAN Notices, 1979
- Final algebra semantics and data type extensionsJournal of Computer and System Sciences, 1979
- Existential quantifiers in abstract data types1979
- The algebraic specification of abstract data typesActa Informatica, 1978
- The Type Free Lambda Calculus1977
- A Course in Mathematical Logic1977
- Specification techniques for data abstractionsIEEE Transactions on Software Engineering, 1975
- CONSTRUCTIVE ALGEBRAS IRussian Mathematical Surveys, 1961