language: en

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

Karl Aberer
TR-91-061 November 1991

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.

[Part of this work was done while the author was at ETH Zurich.]

[Submitted to Journal of Symbolic Computation.]

International Computer Science Institute, Berkeley, CA 94704.
email: aberer@icsi.berkeley.edu.

[Supported by Schweizerische Gesellschaft zur Forderung der Informatik und ihrer Anwendungen]