From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.66.159.227 with SMTP id xf3mr38136767pab.27.1428609730820; Thu, 09 Apr 2015 13:02:10 -0700 (PDT) X-Received: by 10.140.93.14 with SMTP id c14mr470840qge.42.1428609730550; Thu, 09 Apr 2015 13:02:10 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!news.glorb.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!m20no2209627iga.0!news-out.google.com!a41ni33qgf.1!nntp.google.com!j5no592819qga.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Thu, 9 Apr 2015 13:02:10 -0700 (PDT) In-Reply-To: <87k2xle34z.fsf@jester.gateway.sonic.net> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=87.91.37.131; posting-account=hya6vwoAAADTA0O27Aq3u6Su3lQKpSMz NNTP-Posting-Host: 87.91.37.131 References: <44b2e375-8993-4a7e-b81a-6a7b512d2e3e@googlegroups.com> <87k2xle34z.fsf@jester.gateway.sonic.net> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <6993ba55-464e-44e3-84c8-8879176bcb70@googlegroups.com> Subject: Re: BDD package in Ada. From: vincent.diemunsch@gmail.com Injection-Date: Thu, 09 Apr 2015 20:02:10 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Xref: news.eternal-september.org comp.lang.ada:25498 Date: 2015-04-09T13:02:10-07:00 List-Id: Le jeudi 9 avril 2015 17:24:14 UTC+2, Paul Rubin a =E9crit=A0: > One thing I'd ask is what your goals are: do you want to use > BDD's for something? To write an interesting Ada library ? I thought of using BDD for :=20 - solving typical SAT problems, without the need to use an external SAT, solver (in fact I thought it could be much simpler to use BDD than=20 developing a SAT solver !). - Sets and relations problems.=20 > Is the BDD library itself likely to be used inside a critical system? No, not inside. But since BDD is a key technology for Model Checking it is still related to critical systems, as a tool for checking them precis= ely. > I get the impression from the Wikipedia article that a lot of the work > in the library is heuristically finding a good ordering of the > variables. I wonder if you can use an existing SAT or SMT solver for > that, and in fact whether the existing BDD libraries work that way. It is true that finding the best variable ordering is NP-hard, so a SAT solver is required, but I think that most implementations use heuristics to find a =ABgood=BB ordering.=20 Re-implementing MiniSAT in Ada, that's a lot more challenging than developing a BDD library ! :-). Vincent