Set constraints

[William Byrd]

Hey everyone!

I've been looking closely at set constraints again. Claire and Nada
previously (and independently) implemented a form of CLP(Set), based
on the paper:

A. Dovier, C. Piazza, E. Pontelli, and G. Rossi.
Sets and Constraint Logic Programming.
ACM Transaction on Programming Language and Systems, Vol. 22 (5),
Sept. 2000, 861-931.
http://www.math.unipr.it/~gianfr/PAPERS/CLP(SET).TOPLAS00.pdf

We found those implementations too slow to be useful in practice.
I've been reading up more on set constraints--apparently, any general
set constraint system that can handle arbitrary terms (including
variables) as set elements will have at least exponentially many
solutions in the worst case. There are various restrictions to set
constraints that can reduce the cost. I'm still interested in very
general set constraints, though--if the user makes the sets ground,
the solving will be more efficient. If not, they get what they asked
for!

The nicest general algorithm for set constraints that can handle
arbitrary terms appears to be:

Membership-Constraints and Complexity in Logic Programming with Sets
Stolzenburg, Frieder
Frontiers of Combining Systems
1996
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8356&rep=rep1&type=pdf

A potentially slower, and vastly more complicated and ugly algorithm
that produces optimal or almost optimal answers is in:

A Minimality Study for Set Unification
The Journal of Functional and Logic Programming, Volume 1997, No. 7.
A. Dovier, A. Policriti, and G. Rossi.
http://cs.tu-berlin.de/journal/jflp/articles/1997/A97-07/A97-07.html

Alas, even the pseudocode for this algorithm looks super nasty.

I'll probably try implementing the Stolzenburg algorithm, since it
looks relatively straight-forward.

Cheers,

--Will

[Khoa Võ Đăng]

I am interested in this, do you have any update?