Initial and final algebra semantics for data type specifications: two characterisation theorems : (preprint)
Jan Aldert Bergstra, John Vivian Tucker · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1980
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 characterise 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 nwnber of auxiliary functions and conditional equations required are included in both theorems.