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 -- You received this message because you are subscribed to the Google Groups "minikanren" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/minikanren. For more options, visit https://groups.google.com/groups/opt_out.
