A BRICS Mini-Course
August 14 and 15, 1996
Lectures by
Dexter Kozen
Joseph Newton Pew, Professor of Computer Science
Cornell University, Ithaca, NY, USA
Set constraints are equations involving expressions denoting sets of ground terms. They have been used extensively in program analysis and type inference. In this minicourse we will give an introduction to the theory and applications of set constraints.
The course will consist of six hours divided into three two-hour sessions. The first session will cover the basic definitions of set constraints, tree set automata and hypergraphs, closed hypergraphs, and regular solutions, and will cover basic applications in type theory and program analysis.
In the second session, we will discuss the complexity of set constraints and show a hierarchy of complexity results depending on the form of the language. We will also discuss more recent work on complexity of Tarskian set constraints, i.e. set constraints over non-Herbrand models, and constraint logic programming with set constraints.
Finally, in the last session we will go more deeply into the theory of set constraints. In particular we will discuss connections with other typing disciplines, including a duality between ``soft'' and ``hard'' typing, and give an introduction to the theory of rational spaces.