Computation on abstract data types. The extensional approach, with an application to streams
type: Item
instance of: scholarly article
title: Computation on abstract data types. The extensional approach, with an application to streams
zbMATH Open document ID: 0858.03048
DOI: 10.1016/0168-0072(96)88189-9
author: Solomon Feferman
published in: Annals of Pure and Applied Logic
publication date: 1997-03-19T00:00:00Z
review text: 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.
reviewed by: Neculai Curteanu
Mathematics Subject Classification ID: 03D75
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 933091
zbMATH Keywords: \(A\)-stream computation
zbMATH Keywords: general theory of computation
zbMATH Keywords: many-sorted functional structures
zbMATH Keywords: abstract data types
zbMATH Keywords: generalized recursion theory
describes a project that uses: Coq
MaRDI profile type: Publication
full work available at URL: 0168-0072(96)88189-9
OpenAlex ID: W1973997468
cites work: Q4001603
cites work: Computable functionals of finite types
cites work: Q3855168
cites work: Q3890680
cites work: Q4202934
cites work: A new approach to abstract data types, I Informal development
cites work: Q5812175
cites work: Recursive Functionals and Quantifiers of Finite Types I
cites work: Q3281965
cites work: Q5344164
cites work: Q4124327
cites work: Q3734395
cites work: The formal language of recursion
cites work: Effective operations on partial recursive functions
cites work: Shorter Notes: A Note on the Failure of the Relativized Enumeration Theorem in Recursive Function Theory
cites work: Q4108313
cites work: Q4842541
cites work: Q3999156
cites work: Q3141916
Wikidata QID: Q127207578
description: scientific article; zbMATH DE number 933091