Joseph Newton Pew, Jr. Professor of Engineering
PhD Cornell, 1977
My research interests include the theory of computational
complexity, especially complexity of decision problems in logic and algebra, program logic
and semantics, and computational algebra. Recent work includes: new polynomial-time
algorithms for type inference in type systems with subtypes and recursive types;
algorithms solving systems of set constraints as used in program analysis; a unification
algorithm for set constraints and a new constraint logic programming language based on set
constraints; development of the theory of rational spaces
|and their relationship to set constraints;
an algorithm for decomposition of algebraic functions; a new polynomial-time algorithm for
resolution of singularities of plane curves; efficient algorithms for optimal transmission
of encoded video data; optimality results for digital interleavers; and complexity and
completeness results for Kleene algebras with tests. Recently I have begun to investigate
the application of Kleene algebra and the modal mu-calculus to problems in software
Undergraduate Admissions Committee, College of
University Arbitration Panel
Faculty Advisor: Cornell Men's Rugby Football Club
and Johnson Graduate School of Management Rugby Football Club
Program Committees: IEEE Symp. Found. Computer
Science (FOCS), 1996; Fixpoints in Computer Science, Sept. 1998
Supervisory Board: Centre for Basic Research in
Computer Science (BRICS), Aarhus Univ. Organizing Committee: IEEE Symp. Logic in Computer
Organizing Committee: Dagstuhl Seminar on Tree
Automata, Oct. 1997
On the complexity of reasoning in Kleene algebra. Proc.
12th Symp. Logic in Computer Science (LICS), Los Alamitos, CA. (June 1997), 195-202.
Efficient algorithms for optimal video
transmission. Proc. IEEE Data Compression Conf. (DCC'98), (J.A. Storer and M. Cohn
ed.), (March 1998), 229-238 (with Y. Minsky and B. Smith).
Set constraints and logic programming. Information
and Computation 141, 1 (April 1998), 2-25.