Helmut Seidl and Christian Fecht. Propagating Differences: An Efficient New Fixpoint Algorithm for Distributive Constraint Systems. , volume 97-13 of Forschungsbericht, 1997. Universität Trier, Mathematik/Informatik.

Integrating semi-naive fixpoint iteration from deductive data bases [3,2,4] as well as continuations into worklist-based solvers, we derive a new application independent local fixpoint algorithm for distributive constraint systems. Seemingly different efficient algorithms for abstract interpretation like those for linear constant propagation for imperative languages [17] as well as for control-flow analysis for functional languages [13] turn out to be instances of our scheme. Besides this systematizing contribution we also derive a new efficient algorithm for abstract OLDT-resolution as considered in [15,16, 25] for Prolog.

Reference: Bibtex