From: "Alex Aiken" <aiken@cs.berkeley.edu> Subject: last seminar Date: Sat, 7 Dec 2002 22:01:27 -0800 Message-ID: <HEEOLHLEJFFMCPIJCOCJGEKKCCAA.aiken@cs.berkeley.edu> For the final programming systems seminar of the semester, Zhendong Su will sing his swan song and then depart to take up his duties as an assistant professor. Come one, come all, to Zhendong's thesis talk. Alex ========================================= Algorithms for and the Complexity of Subtype Entailment Zhendong Su UC Berkeley Monday, Dec. 9 4-5 PM 310 Soda Hall The decidability of subtype entailment is an important open problem in the design and implementation of scalable and expressive subtype systems and type-based program analyses. The problem, so far, has resisted many competent attacks. In this talk, I will report recent progress towards resolving this problem. In particular, I will show that the first-order theory of subtyping constraints is undecidable, and in the case where all type constructors are unary and constants, it is decidable via an automata-theoretic reduction. In addition, I will present efficient algorithms for entailment with conditional equality constraints, arguably the simplest type language with subtyping.
This archive was generated by hypermail 2b30 : 12/07/02 PST