DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                              ODENSE UNIVERSITY                              

                        Simplification and Complexity                        
                      in Subtype-Based Program Analysis                      

                                 Jakob Rehof                                 
                        Department of Computer Science                       
                           University of Copenhagen                          

                     Tuesday, April 28, 1998, at 2:15 PM                     
                               The Seminar Room                              


Program  analyses  based   on  partial  order   constraints  (e.g.   subtype
constraints, set constraints) suffer  from the problem  that constraint sets
extracted   from   large   programs   become   equally   large.   Constraint
simplification aims at removing  redundant information from  constraint sets
in order to make them more manageable  in polymorphic inference systems, and
the simplification  problem is  now widely  regarded  as a  key problem  for
scalability of polymorphic subtype-based analysis.  In this talk, we give an
overview of our recent  results on algorithms and  complexity for constraint
simplification and constraint satisfaction in several subtyping systems, and
we discuss applications to program analysis based on such systems.

Some of the work discussed in the talk is joint with Fritz Henglein, DIKU.


                                                             Kim Skak Larsen