zbMATH — the first resource for mathematics

The complexity of set constraints. (English) Zbl 0953.68557
Börger, Egon (ed.) et al., Computer science logic. 7th Workshop, CSL ’93, Swansea, GB, September 13-17, 1993. Selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 832, 1-17 (1994).
Summary: 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 constraint language.
For the entire collection see [Zbl 0852.00043].
Reviewer: Reviewer (Berlin)

68Q25 Analysis of algorithms and problem complexity
68Q60 Specification and verification (program logics, model checking, etc.)