Christian Fecht and Helmut Seidl. Propagating Differences: An Efficient New Fixpoint Algorithm for Distributive Constraint Systems. In Chris Hankin, editor, Programming Languages and Systems, volume 1381 of Lecture Notes in Computer Science, pages 90-104, Lisbon, Portugal, April 1998. Springer.

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.

Download: PDF Reference: Bibtex The original publication is available at