The Complexity of Set Constraints
Aiken, Alexander; Kozen, Dexter; Vardi, Moshe; Wimmers, Ed
Set constraints are relations between sets of terms. They have been used extensively in various applications in program analysis and type inference. We present several results on the computational complexity of solving systems of set constraints. The systems we study form a natural complexity hierarchy depending on the form of the language.
computer science; technical report
Previously Published As