COMPUTATION ON ABSTRACT-DATA-TYPES - THE EXTENSIONAL APPROACH, WITH AN APPLICATION TO STREAMS

In this paper we specialize the notion of abstract computational proce dure previously introduced for intensionally presented structures to t hose which are extensionally given. This is provided by a form of gene ralized recursion theory which uses schemata for explicit definition, conditional definition and least fixed point (LFP) recursion in functi onals of type level less than or equal to 2 over any appropriate struc ture. It is applied here to the case of potentially infinite (and more general partial) streams as an abstract data type.