Nordic Journal of Computing Bibliography

Christian Fecht and Helmut Seidl. Propagating Differences: an Efficient New Fixpoint Algorithm for Distributive Constraint Systems. Nordic Journal of Computing, 5(4):304-329, Winter 1998.

Integrating semi-naive fixpoint iteration from deductive data bases [3,2,4] (François Bancilhon and Raghu Ramakrishnan: An amateur's introduction to recursive query processing strategies. In ACM SIGMOD Conference, 1986, 16-52; Isaac Balbin and Kotagiri Ramamohanarao: A generalization of the differential approach to recursive query evaluation. Journal of Logic Programming (JLP) 4, 3, 1987, 259-262; François Bancilhon and Raghu Ramakrishnan: Performance evaluation of data intensive logic programs. In Foundations of Deductive Databases.) 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] (Susan Horwitz, Thomas W. Reps, and Mooly Sagiv: Precise interprocedural dataflow analysis with applications to constant propagation. In Proceedings of 6th International Conference on Theory and Practice of Software Development (TAPSOFT), Volume 915 of LNCS, Springer-Verlag, 1995, 651-665.) as well as for control-flow analysis for functional languages [12] (Nevin Heintze: Set-based analysis of ML programs. In ACM Conference on Lisp and Functional Programming (LFP), 1994, 306-317.) 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] (Pascal Van Hentenryck, Olivier Degimbe, Baudouin Le Charlier, and Laurent Michel: Abstract Interpretation of Prolog based on OLDT resolution. Technical Report CS-93-05, Brown University, Providence, RI 02912, 1993; Pascal Van Hentenryck, Olivier Degimbe, Baudouin Le Charlier, and Laurent Michel: The impact of granularity in abstract interpretation of Prolog. In Proceedings of Static Analysis, 3rd International Workshop (WSA), Volume 724 of LNCS, Springer-Verlag, 1993, 1-14; Helmut Seidl and Christian Fecht: Interprocedural analysis based on PDAs. Technical Report 97-06, University Trier, 1997, Extended Abstract in: Verification, Model Checking and Abstract Interpretation A Workshop in Association with ILPS'97. Long version to appear in Journal of Logic Programming (JLP).) for Prolog.

Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors; F.3.1 [Logics and Meanings of Programs]: Specifying and Verifying and Reasoning about Programs; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval

Additional Key Words and Phrases: fixpoint computation, semi-naive iteration, program analysis

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database