I see. What is the task in detail? Are some of the set fixed or known in advance? What's the argument against a bitset-based solution?
Cheers, Steffen Am 27. Oktober 2017 19:10:35 MESZ schrieb Stephane Ducasse <stepharo.s...@gmail.com>: >It was for test inclusion of UTF-8 characters so we do not want to >rely on external libraries. > >On Fri, Oct 27, 2017 at 1:54 PM, Steffen Märcker <merk...@web.de> >wrote: >> Dear Andrew, >> >> I didn't find time to answer earlier. Some time ago, I was looking >for a >> (MT)BDD package in ST as well. I didn't found one. So the only two >options >> left are >> >> 1) implementing a new BDD lib in ST and >> 2) doing FFI to some existing lib, e.g. CUDD, Sylvan, Jinc >> >> I'd prefer 2) since the existing libraries are feature-rich and >highly >> optimized - which took quite some time. As a bonus, a solution could >> potentially switch between those backends. The biggest hurdle, in my >option, >> is memory management, since most libs use some sort of reference >counting. >> And you do not want to end up with nightmarish dozens of ref(bddNode) >> deref(bddNode) in your application code (like the probabilistic model >> checker PRISM does). This introduces hard to track bugs easily. >However, I >> have an idea in mind how to tackle this but I didn't found the time >to put >> it into code yet. >> >> May I ask, which sort of application do you have in mind? >> >> Best, Steffen >> >> >> >> >> Am .10.2017, 07:54 Uhr, schrieb Prof. Andrew P. Black ><bl...@cs.pdx.edu>: >> >>> Thanks for the responses so far. I see that I need to clarify my >enquiry. >>> >>> B-Trees and BDDs are not the same. BDDs are an efficient and >compact >>> representations for Boolean functions, sometimes used in SAT-solvers >and >>> electronics design. The key idea is that since the output must be >0 or 1, >>> you can represent any Boolean function as a tree whose depth is the >same as >>> the number of bits in the input. >>> >>> To make the tree small and efficient, though, you need to eliminate >any >>> node whose two children are the same, and to share subtrees, so that >you >>> really get a DAG, not a tree. The full name for these efficient >compressed >>> trees is “Reduced Order Binary Decision Diagrams”, or ROBDDs. I was >hoping >>> that someone else had implemented the algorithms necessary to build >this >>> representation. >>> >>> Because sets can be considered to be Booleans functions (true => >argument >>> is in the set), you can use ROBDDs to efficiently represent large >sets. >>> >>> To be clear, despite the word “diagram” in the name, one is not >normally >>> interested in drawing the BDD — except in the documentation for the >package >>> ;-). Normally, BDDs they are used to represent sets, or functions, >where >>> the drawing would be hopelessly large. >>> >>> The BuDDy package (http://buddy.sourceforge.net/manual/main.html) is >an >>> example of what I’m looking for, but unfortunately it’s in C++. >>> >>> Andrew >>> >>> >>>> On 25 Oct 2017, at 21:39 , Stephane Ducasse ><stepharo.s...@gmail.com> >>>> wrote: >>>> >>>> Hi andrew >>>> >>>> I think that Avi did a package about BDD (but I thought it was >special >>>> binary trees) so this is probably the same. >>>> Did you check on Squeaksource? >>>> http://www.squeaksource.com/BTree.html >>>> If this is what you are looking for I can help porting it to Pharo. >>>> >>>> Stef >>>> >>>> >>>> On Wed, Oct 25, 2017 at 9:02 PM, Prof. Andrew P. Black ><bl...@cs.pdx.edu> >>>> wrote: >>>>> >>>>> Does anyone know of a BDD — that’s Binary Decision Diagram — >package >>>>> written in Smalltalk? >>>>> >>>>> Andrew >>>>> >>>>> >>>> >>> >>
