Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 99151

Program Analysis

( Apr 11 – Apr 16, 1999 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:

  • H. Riis Nielson (Aarhus)
  • M. Sagiv (Tel Aviv)


Program analysis offers static techniques for predicting safe and computable approximations to the set of values or behaviors arising dynamically during the execution of programs. Traditionally, program analysis has been used in optimizing compilers; more recent applications include the validation of safety properties of software for embedded systems, and also program analysis shows promise of becoming an important ingredient in ensuring the acceptable behavior of software components roaming around on information networks.

Over the years a number of different approaches have been developed for program analysis, all of which have a quite extensive literature. To give an impression of the diversity let us briefly mention some of the main approaches: The flow based approach includes the traditional data flow analysis techniques for mainly imperative languages, but also control flow analysis as developed for functional and object oriented languages, and set based analysis as developed for logic and functional languages. The model based approach includes the parameterized denotational semantics techniques developed for functional and imperative languages, but also more generally the use of mathematical modeling in the abstract interpretation of imperative, functional, concurrent and logic languages. The inference based approach includes general logical techniques touching upon program verification techniques, but also the type and effect systems developed for functional, imperative and concurrent languages. For each of the approaches there are theoretical studies of semantic and algorithmic properties as well as practical experiments exploiting the feasibility of the techniques.

Typically, the various techniques have been developed and further refined by subcommunities -- with the result that often the commonalties between analogous developments are not sufficiently appreciated. To guide the research effort in our community, it is necessary with an appraisal of the current technology: we need to understand the strengths and weaknesses of the different approaches, and the extent to which insights developed for one approach can be used to enhance the power of other approaches. The usual measures for strengths of program analysis techniques are:

  • Generality: to which class of programs can the techniques be applied?
  • Precision: how precise are the results of the analysis? can the analysis guarantee a certain level of precision for a given class of programs (this question becomes more important when program analysis is used in application domains such as testing and software engineering)?
  • Efficiency: how long does it take to run the analysis and does it scale up for large programs?

For example, some static analysis techniques limit the size or type of input programs but yield precise results, while others handle programs of arbitrary size and type but without being overly precise.

We believe that a Dagstuhl seminar will be an ideal setting for the subcommunities to share their experience. We are aware that the gap between some of the communities are larger than between others -- to ensure the success of the meeting we have therefore decided not to cover the full spectrum of approaches in this meeting. Also, to help achieving our goal, we plan to invite 6-8 of the participants to give longer talks (60-90 minutes) with more detailed accounts of particular techniques that we believe should be of general interest or that represent important tools or techniques that seem to be somewhat overlooked. The remainder of the talks are expected to be shorter (approx.~30 minutes) and present current work.

  • H. Riis Nielson (Aarhus)
  • M. Sagiv (Tel Aviv)