Constraint Propagation as Information Maximization
  This paper draws on diverse areas of computer science to develop a unified
view of computation:
  (1) Optimization in operations research, where a numerical objective function
is maximized under constraints, is generalized from the numerical total order
to a non-numerical partial order that can be interpreted in terms of
information. (2) Relations are generalized so that there are relations of which
the constituent tuples have numerical indexes, whereas in other relations these
indexes are variables. The distinction is essential in our definition of
constraint satisfaction problems. (3) Constraint satisfaction problems are
formulated in terms of semantics of conjunctions of atomic formulas of
predicate logic. (4) Approximation structures, which are available for several
important domains, are applied to solutions of constraint satisfaction
problems.
  As application we treat constraint satisfaction problems over reals. These
cover a large part of numerical analysis, most significantly nonlinear
equations and inequalities. The chaotic algorithm analyzed in the paper
combines the efficiency of floating-point computation with the correctness
guarantees of arising from our logico-mathematical model of
constraint-satisfaction problems.
