In this paper, we introduce the class of co-definite set constraints. This is a natural subclass of set constraints which,
when satisfiable, have a greatest solution. It is practically motivated by the set-based analysis of logic programs with the greatest-model semantics. We present
an algorithm solving co-definite set constraints and show that their satisfiability problem is DEXPTIME-complete.
On leave from Wroclaw University. Partially supported by Polish KBN grant 8T11C02913.