Combining Norms to Prove Termination

1. F. Benoy and A. King. Inferring argument size relationships with CLP(R). In Sixth International Workshop on Logic Program Synthesis and Transformation (LOPSTR’96), pages 204–223, 1996.

   Google Scholar 

2. A. Bossi, N. Cocco, and M. Fabris. Proving termination of logic programs by exploiting term properties. In S. Abramsky and T.S.E. Maibaum, editors, Proceedings of Tapsoft 1991, volume 494 of Lecture Notes in Computer Science, pages 153–180. Springer-Verlag, Berlin, 1991.

   Google Scholar 

3. Annalisa Bossi, Nicoletta Cocco, and Massimo Fabris. Typed norms. In B. Krieg-Brückner, editor, Proceeedings ESOP’ 92, volume 582 of Lecture Notes in Computer Science, pages 73–92. Springer-Verlag, Berlin, 1992.

   Google Scholar 

4. A. Brodsky and Y. Sagiv. Inference of monotonicity constraints in Datalog programs. In Proceedings of the Eighth ACM SIGACT-SIGART-SIGMOD Symposium on Principles of Database Systems, pages 190–199, 1989.

   Google Scholar 

5. Maurice Bruynooghe, Wim Vanhoof, and Michael Codish. Pos(t): Analyzing dependencies in typed logic programs. Technical report, Presented at the Andrei Ershov Fourth International Conference on Perspectives of System Informatics, July 2001.

   Google Scholar 

6. M. Codish and C. Taboch. A semantic basis for the termination analysis of logic programs. The Journal of Logic Programming, 41(1):103–123, 1999.

   Article  MATH  MathSciNet  Google Scholar 

7. Patrick Cousot and Nicholas Halbwachs. Automatic discovery of linear restraints among variables of a program. In Proceedings of the Fifth Annual ACM Symposium on Principles of Programming Languages, pages 84–96, January 1978.

   Google Scholar 

8. D. De Schreye and K. Verschaetse. Deriving linear size relations for logic programs by abstract interpretation. New Generation Computing, 13(02):117–154, 1995.

   Article  Google Scholar 

9. Danny De Schreye and Stefaan Decorte. Termination of logic programs: the neverending story. The Journal of Logic Programming, 19 & 20:199–260, May 1994.

   Google Scholar 

10. Stefaan Decorte, Danny de Schreye, and Massimo Fabris. Automatic inference of norms: A missing link in automatic termination analysis. In Dale Miller, editor, Logic Programming-Proceedings of the 1993 International Symposium, pages 420–436, Massachusetts Institute of Technology, Cambridge, Massachusetts 021-42, 1993. The MIT Press.

    Google Scholar 

11. Stefaan Decorte, Danny De Schreye, and Massimo Fabris. Integrating types in termination analysis. Technical Report CW 222, K.U. Leuven, Department of Computer Science, January 1996.

    Google Scholar 

12. Stefaan Decorte, Danny De Schreye, and Massimo Fabris. Exploiting the power of typed norms in automatic inference of interargument relations. Technical Report CW 246, K.U. Leuven, Department of Computer Science, January 1997.

    Google Scholar 

13. R. W. Floyd. Assigning meanings to programs. In J.T Schwartz, editor, Proceedings of Symposium in Applied Mathematics, volume 19, Mathematical Aspects of Computer Science, pages 19–32, NewYork, 1967. American Mathematical Society, Providence, RI.

    Google Scholar 

14. J. Gallagher and G. Puebla. Abstract Interpretation over Non-Deterministic Finite Tree Automata for Set-Based Analysis of Logic Programs. In Shriram Krishnamurthi and C. R. Ramakrishnan, editors, Practical Aspects of Declarative Languages, 4th International Symposium, PADL 2002, Portland, OR, USA, January 19–20, 2002, volume 2257 of Lecture Notes in Computer Science, pages 243–261. Springer, 2002.

    Google Scholar 

15. Samir Genaim and Michael Codish. Inferring termination conditions for logic programs using backwards analysis. In R. Nieuwenhuis and A. Voronkov, editors, Proceedings of the Eighth International Conference on Logic for Programming, Artificial Intelligence and Reasoning, volume 2250 of Lecture Notes in Artificial Intelligence, pages 681–690. Springer-Verlag, December 2001.

    Google Scholar 

16. M. Karr. Affine relationships among variables of a program. Acta Informatica, 6:133–151, 1976.

    Article  MATH  MathSciNet  Google Scholar 

17. Andy King, Kish Shen, and Florence Benoy. Lower-bound time-complexity analysis of logic programs. In Jan Maluszynski, editor, International Symposium on Logic Programming, pages 261–276. MIT Press, November 1997.

    Google Scholar 

18. V. Lagoon and P. Stuckey. A framework for analysis of typed logic programs. In FLOPS, volume 2024 of Lecture Notes in Computer Science, pages 296–310. Springer-Verlag, Berlin, 2001.

    Google Scholar 

19. N. Lindenstrauss and Y. Sagiv. Automatic termination analysis of logic programs. In Lee Naish, editor, Proceedings of the Fourteenth International Conference on Logic Programming, pages 63–77, Leuven, Belgium, 1997. The MIT Press.

    Google Scholar 

20. K. Marriott and H. Søndergaard. Precise and efficient groundness analysis for logic programs. ACM Letters on Programming Languages and Systems, 2(1–4):181–196, 1993.

    Article  Google Scholar 

21. Jon Martin and Andy King. Typed norms for typed logic programs. In Logic Program Synthesis and Transformation. Springer-Verlag, August 1996. Available at http://www.cs.ukc.ac.uk/pubs/1996/511.

22. F. Mesnard and U. Neumerkel. Applying static analysis techniques for inferring termination conditions of logi programs. In Static Analysis Symposium, 2001.

    Google Scholar 

23. L. Sterling and E. Shapiro. The Art of Prolog. MIT Press, second edition, 1994.

    Google Scholar 

24. W. Vanhoof and M. Bruynooghe. When size does matter. Preproceedings of the Eleventh International Workshop on Logic-based Program Synthesis and Transformation (LOPSTR), November 2001.

    Google Scholar 

25. E. Yardeni and E.Y. Shapiro. A type system for logic programs. Journal of Logic Programming, 10(2):125–154, 1990.

    Article  MathSciNet  Google Scholar 

Download references