A BRICS Mini-Course
February 21, 24 and 25, 2003
Lectures by
Abbas Edalat, ae@doc.ic.ac.uk
Professor of Computer Science and Mathematics
Department of Computing, Imperial College, London, UK
We present a domain-theoretic synthesis of two major paradigms of modern science and technology: Differential Calculus introduced by Newton and Leibnitz in the 17th century and Computer Science, introduced by Alan Turing in the 20th century. We extend the notions of the indefinite integral and the derivative to Scott continuous interval-valued functions of a real variable and obtain a domain-theoretic generalization of the Fundamental Theorem of Calculus. Then a continuous Scott domain for continuously differentiable functions is constructed which is composed of consistent pairs of Scott continuous functions, each pair providing a function approximation and a derivative approximation for a classical continuously differentiable function. The set of continuously differentiable functions with their sup norm is embedded into the set of maximal elements of this domain.
We then present a domain-theoretic framework for solving differential equations. Given a continuous vector field, uniformly Lipschitz in the space component, and an initial value, a domain-theoretic generalization of the classical Picard operator is defined on the domain for continuously differentiable functions. This operator successively updates the function approximation and the derivative approximation to produce better and better refined approximations to the solution of the differential equations, enabling us to compute the solution up to any given precision, a distinguishing feature that is unique to the domain-theoretic technique. The framework also allows us to tackle differential equations when the vector field and/or the initial value are uncertain or imprecise.
We finally present a domain-theoretic synthesis of Computational Geometry and Computer Science. We present a domain for geometric objects in the n-dimensional Euclidean space, which for the first time enables us to define the notions of a computable geometric object and operation. In contrast to classical models, all basic operations such as membership and Boolean operations are continuous and computable in this model, which also supports the design of robust geometric algorithms. We illustrate this with domain-theoretic robust algorithms for the Convex Hull, Voronoi Diagram and Delaunay triangulation.
(This mini-course is based mostly on joint work with Andre Lieutier, Dassault Systemes, Aix-en-Province. Ali Khanban and Marko Krznaric, Imperial, have also contributed to some of the algorithmic parts of the work. Papers on this subject can be obtained from http://www.doc.ic.ac.uk/ ae/papers.html)