Re: BDD package in Ada.

[Georg Bauhaus <bauhaus@futureapps.invalid>]

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?