Combinatory Differential Fields: An Algebraic Approach to Approximate Computation and Constructive Analysis

TitleCombinatory Differential Fields: An Algebraic Approach to Approximate Computation and Constructive Analysis
Publication TypeTechnical Report
Year of Publication1991
AuthorsAberer, K.
Other Numbers691
Abstract

The algebraic structure of combinatory differential fields is constructed to provide a semantics for computations in analysis. In this setting programs, approximations, limits and operations of analysis are represented as algebraic terms. Analytic algorithms can be derived by algebraic methods. The main tool in this construction are combinatory models which are inner algebras of Engeler graph models. As an universal domain of denotational semantics the lattice structure of the graph models allows to give a striking simple semantics for computations with approximations. As models of combinatory algebra they provide all essential computational constructs, including recursion. Combinatory models are constructed as extensions of first order theories. The classical first order theory to describe analysis is the theory of differential fields. It turns out that two types of computational constructs, namely composition and piecewise definition of functions, are preferably introduced as extensions of the differential fields theory. Combinatory differential fields are then the combinatory models of these enriched differential fields. We show for basic algorithms of computational analysis how their combinatory counterparts are derived in the algebraic setting. We illustrate how these algorithms are suitable to be implemented in a computer algebra environment like mathematica.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1991/tr-91-061.pdf
Bibliographic Notes

ICSI Technical Report TR-91-061

Abbreviated Authors

K. Aberer

ICSI Publication Type

Technical Report