Computation on abstract data types. The extensional approach, with an application to streams (Q1923575)

The paper continues the author's previous results on a general theory of computation to be applied to many-sorted functional structures as abstract data types. The proposed approach is based on a form of generalized recursion theory which uses schemata for explicit definition, conditional definition and least fixed point recursion in functionals of type level less than two over any appropriate structure. One of the main contributions of the paper is to separate the extensional part of the proposed theory and to show how abstract computational procedures may be applied to \(A\)-streams (with \(A\) an arbitrary set), in particular to finite nonterminating streams, to infinite streams, and even to more general (``gappy'') streams.