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=-0.3 required=5.0 tests=BAYES_00,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Newsgroups: comp.lang.ada
Subject: Re: BDD package in Ada.
Date: Thu, 9 Apr 2015 11:29:38 +0200
Organization: cbb software GmbH
Message-ID: <dgopthig9xl9$.lwptg6zjviel.dlg@40tude.net>
References: <44b2e375-8993-4a7e-b81a-6a7b512d2e3e@googlegroups.com>
 <1miph3v72f4y2$.1u76w2ujg74zf$.dlg@40tude.net>
 <c7db12c1-10fa-40ee-a2df-ff8a8b2177bc@googlegroups.com>
 <mg46ko$u76$1@loke.gir.dk> <mg5fcg$maf$1@dont-email.me>
Reply-To: mailbox@dmitry-kazakov.de
NNTP-Posting-Host: w2sqUGEBZqsVBYNL7Ky3Kg.user.speranza.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
X-Complaints-To: abuse@aioe.org
User-Agent: 40tude_Dialog/2.0.15.1
X-Notice: Filtered by postfilter v. 0.8.2
Xref: news.eternal-september.org comp.lang.ada:25485
Date: 2015-04-09T11:29:38+02:00
List-Id: <comp.lang.ada>

On Thu, 09 Apr 2015 11:06:18 +0200, Georg Bauhaus wrote:

> On 08.04.15 23:30, Randy Brukardt wrote:
>> "Vincent DIEMUNSCH" <vincent.diemunsch@gmail.com> wrote in message
>> news:c7db12c1-10fa-40ee-a2df-ff8a8b2177bc@googlegroups.com...
>>> Le mercredi 8 avril 2015 08:38:19 UTC+2, Dmitry A. Kazakov a �crit :
>>
>>>> I would not call it "fundamental". It is simply a tree with factored out
>>>> subtrees. Need not to be binary, BTW.
>>> A BINARY decision diagram needs to be binary, by definition. It is not
>>> "simply" a tree,
>>> but a highly optimised data structure, not only by factoring the tree, but
>>> through variable
>>> ordering, which is the key idea. (Briant's paper is about ORDERED BDD). It
>>> is usefull for the implementation of Sets and operations on sets.
>>
>> Sounds like premature optimization to me.
> 
> The presentations say that in the worst case, some fundamental operations
> are O(linear) if the graph is ordered, but are O(exponential) if not.
> I am not sure, then, if that makes "premature optimization" an adequate
> characterization.
>
> If a compiler needs to sort out whether or not something-and-then-this-and-...
> -then-if-that...-and-finally-this, then wouldn't the above ordering of Boolean
> trees have a major impact on feasibility?

For decision threes even more important is the order in which features
(questions at the nodes) get tested, both in terms of complexity and the
results obtained when some choices are implied (missing nodes). Therefore
trees are frequently rotated to change the order. Everybody knows this
problem from programming when writes nested if's and/or cases. Which
variable to test first? The code greatly depends on the order, as well as
ability to factor out common paths.

With low-level structures, you never can tell what is optimization and what
is a property. That is why there are many graph implementation but when you
need one, you have to design it new.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de