Combinatory Differential Fields: An Algebraic Approach to Approximate Computation and Constructive Analysis
Title | Combinatory Differential Fields: An Algebraic Approach to Approximate Computation and Constructive Analysis |
Publication Type | Technical Report |
Year of Publication | 1991 |
Authors | Aberer, K. |
Other Numbers | 691 |
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. |
URL | http://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 |