Leszek Pacholski

University of Wroclaw

Solving Set Constraints

DIMACS Center - Room 431
Busch Campus
Piscataway, New Jersey
June 14, 2:30 p.m.


Systems of set constraints describe relations between sets of ground terms; they have the form of inclusions between set expressions built over a set of set-valued variables, constants and function symbols. Set constraints have been successfully used in program analysis and type inference algorithms for functional, imperative and logic programming languages by a number of researchers. Solving a system of set constraints is the main part of these algorithms.

The satisfiability problem for such constraints was studied by many researchers. The complexity of these problems has also been considered. In my talk, I shall give some hints of how set constraints can be applied and shall provide the main ideas behind the decidability and complexity results. Finally I shall mention recent applications to concurrent programs.