I am interested in this, do you have any update? On Saturday, February 15, 2014 at 9:56:03 AM UTC+2, William Byrd wrote: > > 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 https://groups.google.com/group/minikanren. For more options, visit https://groups.google.com/d/optout.
