Propagating differences: an efficient new fixpoint algorithm for distributive constraint systems
Christian Fecht, Helmut Seidl · 1998
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 [16] as well as for control-flow analysis for functional languages [12] 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 [14, 15, 24] for Prolog.