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!.POSTED!not-for-mail
From: Georg Bauhaus <bauhaus@futureapps.invalid>
Newsgroups: comp.lang.ada
Subject: Re: BDD package in Ada.
Date: Thu, 09 Apr 2015 11:06:18 +0200
Organization: A noiseless patient Spider
Message-ID: <mg5fcg$maf$1@dont-email.me>
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>
Reply-To: nonlegitur@futureapps.de
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 9 Apr 2015 09:05:20 +0000 (UTC)
Injection-Info: mx02.eternal-september.org;
 posting-host="d68acf24438183586df3e084645e1d30";
	logging-data="22863"; mail-complaints-to="abuse@eternal-september.org";
	posting-account="U2FsdGVkX19E+jidRk0Wa5RJP6j8/TNhfrtB+JkLFiQ="
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9;
 rv:31.0) Gecko/20100101 Thunderbird/31.6.0
In-Reply-To: <mg46ko$u76$1@loke.gir.dk>
Cancel-Lock: sha1:0TfN7uMafmQ2rwYb8VqWMhyN82I=
Xref: news.eternal-september.org comp.lang.ada:25484
Date: 2015-04-09T11:06:18+02:00
List-Id: <comp.lang.ada>

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?