Static Monotonicity Analysis for λ-definable Functions over Lattices

1. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.

   Google Scholar 

2. Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of The ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 238–252, 1977.

   Google Scholar 

3. Patrick Cousot and Radhia Cousot. Abstract interpretation frameworks. Journal of Logic Computation, 2(4):511–547, 1992. Also as a tech report: Ecole Polytechnique, no. LIX/RR/92/10.

   Article  MATH  MathSciNet  Google Scholar 

4. Patrick Cousot and Radhia Cousot. Compositional and inductive semantic definitions in fixpoint, equational, constraint, closure-condition, rule-based and game-theoretic form. In Lecture Notes in Computer Science, volume 939, pages 293–308. Springer-Verlag, proceedings of the 7th international conference on computer-aided verification edition, 1995.

   Google Scholar 

5. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. Number Report TR99-107 in Electronic Colloquium on Computational Compleity, June 1999.

   Google Scholar 

6. Oded Goldreich, Shafi Goldwasser, Eric Lehman, and Dand Ron. Testing monotonicity. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998.

   Google Scholar 

7. B. Le Charlier and P. Van Hentenryck. A universal top-down fixpoint algorithm. Technical Report TR-CS-92-25, Brown University, Dept. of Computer Science, May 1992. (also as a technical report of Institute of Computer Science, University of Namur).

   Google Scholar 

8. B. Le Charlier and P. Van Hentenryck. Experimental Evaluation of a Generic Abstract Interpretation Algorithm for Prolog. ACM Transactions on Programming Languages and Systems, 16(1):35–101, January 1994.

   Article  Google Scholar 

9. Florian Martin. PAG — an efficient program analyzer generator. International Journal on Software Tools for Technology Transfer, 2(1):46–67, 1998.

   Article  MATH  Google Scholar 

10. J. A. Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1):23–41, 1965.

    Article  MATH  Google Scholar 

11. D.E. Rutherford. Introduction to Lattice Theory. Hafner Publishing Company, New York, 1965.

    MATH  Google Scholar 

12. Winfrid G. Schneeweiss. A necessary and sufficient criterion for the monotonicity of boolean functions with deterministic and stochastic. IEEE Transactions on Computers, 45(11):1300–1302, November 1996.

    Article  MATH  MathSciNet  Google Scholar 

13. Jean-Pierre Talpin and Pierre Jouvelot. Type, effect and region reconstruction in polymorphic functional languages. In Proceedings of Functional Programming Languages and Computer Architecture, 1991.

    Google Scholar 

14. Jean-Piere Talpin and Pierre Jouvelot. Polymorphic type, region and effect inference. Journal of Functional Programming, 2(3):245–271, July 1992.

    Article  MATH  MathSciNet  Google Scholar 

15. Mads Tofte and Jean-Pierre Talpin. A theory of stack allocation in polymorphically typed languages. Technical Report Technical Report 93/15, Department of Computer Science, Copenhagen University, July 1993.

    Google Scholar 

16. Mads Tofte and Jean-Pierre Talpin. Implementation of the typed call by-value λ-calculus using a stack of regions. In Proceedings of The ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 188–201, January 1994.

    Google Scholar 

17. Andrei Voronenko. On the complexity of the monotonicity verification. In Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pages 4–7, July 2000.

    Google Scholar 

18. Kwangkeun Yi and Williams Ludwell Harrison III. Automatic generation and management of interprocedural program analyses. In Proceedings of The ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 246–259, January 1993.

    Google Scholar 

19. Kwangkeun Yi. Program Analysis System Zoo. Research On Program Analysis: National Creative Research Center, KAIST, July 2001. http://ropas.kaist.ac.kr/zoo/doc/rabbit-e.ps.

20. Kwangkeun Yi. System Zoo: towards a realistic program analyzer generator, July 2001. Seminar talk at ENS, Paris. http://ropas.kaist.ac.kr/~kwang/talk/ens01/ens01.ps.

21. Kwangkeun Yi and Sukyoung Ryu. Towards a cost-effective estimation of uncaught exceptions in SML programs. In Proceedings of the 4th International Static Analysis Symposium, volume 1302 of Lecture Notes in Computer Science, pages 98–113. Springer-Verlag, 1997.

    Google Scholar 

22. Kwangkeun Yi and Sukyoung Ryu. A cost-effective estimation of uncaught exceptions in Standard ML programs. Theoretical Computer Science, 273(1), 2001. (to appear).

    Google Scholar 

Download references