Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Better compression for a positive DNF than via BDD
26 views
Skip to first unread message
Jan Burse
Sep 9, 2012, 1:16:51 PM9/9/12
to
Dear All,
I am experimenting with compressing positive disjunctive normal form
(DNF). When I use binary decision diagrams (BDDs) related algorithms I
don't get very good results.
Here is an example of the desired compression:
Input:
(p & q & s & t) v
(p & r & s & t) v
(p & q & s & u) v
(p & r & s & u) v
w.
Output:
(p & (q v r) & s & (t v u)) v
w.
Do such algorithms exits? Are they time or space intensive?
Bye
I am experimenting with compressing positive disjunctive normal form
(DNF). When I use binary decision diagrams (BDDs) related algorithms I
don't get very good results.
Here is an example of the desired compression:
Input:
(p & q & s & t) v
(p & r & s & t) v
(p & q & s & u) v
(p & r & s & u) v
w.
Output:
(p & (q v r) & s & (t v u)) v
w.
Do such algorithms exits? Are they time or space intensive?
Bye
0 new messages