Call for Papers

Third International Workshop


Set Constraints

and Constraint-based Program Analysis

Schloss Hagenberg, Austria

November 1, 1997

Scope of the Conference

Set constraints are a calculus for reasoning about relationships between sets of values. Expressions in this calculus are built from variables, the set operations union, intersection and complement as well as set versions of the functions associated with the underlying universe of values. Set constraints consist of containment and equality relationships between these expressions.

The first uses of set constraints date back at least to John Reynold's early work on program analysis in 1969. In the last decade there has been a significant increase in the interest in set constraints, with major advances both in the foundations of set constraints as well as in applications. We now have algorithms and complexity characterizations for a large variety of classes of set constraints. Connections have been established between set constraints and various fragments of logic, including the theory of $k$ successors, tree automaton, and monadic logic. Meanwhile, constraints have become a core technology in areas such as types and program analysis. Constraint-based approaches have led to many algorithmic and conceptual advances in type inference (particularly subtypes), data-flow analysis, control-flow analysis, binding-time analysis, and sorted-unification. Many of these works directly use set constraints; other used equational and constraint theories of which set constraints are a generalization.

The aim of this workshop is to bring together researchers working on all aspects of set constraints, and provide a forum for discussing novel applications, implementation, new results and open problems. We also hope that the workshop will give a sense of the diversity of set constraints applications, and in so doing generate new problems, approaches, and opportunities.


The workshop will take place at Schloss Hagenberg, near Linz, Austria, in connection with CP97, the Third International Conference on Principles and Practice of Constraint Programming.

Submission Details

Authors are invited to submit short papers (2-8 pages) for presentation at the workshop, preferrably by email to We anticipate distributing a proceedings of accepted papers. Papers may describe preliminary or partial results as well as finished research. Position papers are also welcome. Topics of interest include, but are not limited to:
- decision procedures and algorithms
- set constraints over new domains (e.g. arithmetic)
- applications
- implementation
- connections with other areas

Submissions deadline: September 30
Acceptance decisions: October 6
Camera-ready deadline: October 20
Workshop: November 1

Organizing Committee:

Alexander Aiken (UC Berkeley, U.S.A.,
Harald Ganzinger (Max Planck Institute, Germany,
Nevin Heintze (Bell Laboratories, U.S.A.,
Joxan Jaffar (National Univ. of Singapor,
Bruno Legeard (Univ. of Franche-Comté,
David McAllester (AT&T Laboratories, U.S.A.,
Leszek Pacholski (University of Wroclaw, Poland,
Jens Palsberg (Purdue University,
Andreas Podelski (Max Planck Institute, Germany,
Jean-Francois Puget (ILOG, France,
Jakob Rehof (DIKU, Denmark,
Sophie Tison (University of Lille, France,

Andreas Podelski
Last modified: Wed Sep 17 15:26:13 MET DST 1997