A sound interval constraint logic programming system.

摘要

This thesis presents the design and implementation of a sound interval Constraint Logic Programming (CLP) system, which is based on sound sequential and parallel interval arithmetic solvers for systems of linear and non-linear constraints, where soundness implies that no solution will be missed. The dissertation has 3 parts. In the first part, we present new interval arithmetic narrowing routines for multiplication and addition as well as for the elementary functions (exp, log, sin). The algorithms presented here are proved correct assuming that the underlying arithmetic conforms to IEEE 754. The algorithms are also reasonably fast and near optimally precise. In the second part, we present parallel implementations of various narrowing strategies for sound constraint solving. In the third part, we deal with the problem of soundly solving linear systems of constraints inside a non-linear interval arithmetic system.