Computer Science Colloquium
Mathematical Analysis of Programs
Sriram Sankaranarayanan
Stanford University
Monday, March 21, 2005 11:15 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 100121185
Directions: http://cs.nyu.edu/csweb/Location/directions.html
Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html
Hosts:
Richard Cole cole@cs.nyu.edu, (212) 9983119
Abstract
Numerical programs are imperative programs over integer and real
quantities. Such programs are ubiquitous. Common examples include
scientific and systems programs, models of control systems such as
timed and hybrid automata, and models of biological systems such as
biochemical reaction mechanisms and gene regulatory networks. Static
analyses of these programs automatically infer properties about the
systems' runtime behaviours, for example, the reachability of a target
set of states, deadlock freedom, and bounds on variables.
In this talk, I demonstrate powerful analyses for both linear and
nonlinear numerical programs using computational tools from algebra
and geometry.
I first consider analyses for linear systems. Traditional
polyhedrabased analyses do not scale due to the high complexity of
polyhedral operations. I present a scalable polynomial time analysis
that works by posing many linear programming queries, which can be
solved by algorithms such as Simplex. The resulting analysis is
precise and scales well on benchmark examples.
Next, I present an analysis for nonlinear systems. Using computational
tools from algebraic geometry such as Groebner bases, the method
infers invariants for many classes of nonlinear systems, including
hybrid systems. I demonstrate the technique and its applications on a
few examples.
top  contact webmaster@cs.nyu.edu
