Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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. For example the algorithms for BDDs that use sharing, it would still show similar branches during printing and/or introduce new prepositional variables, both things are not desired:

Example: Compression (Bad)
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 & s & (t v u)) v (r & s & (t v u)))) v
  w.

- or -

Output:
  (p & ((q & h) v (r & h)) & (h <-> s & (t v u))) v
  w.

The result should be a single formula, not anymore DNF, which is more compact than the binary decision diagram algorithms which uses only disjunction and conjunction, and the prepositional variables already found in the original DNF. Here is an example of the desired compression:

Example: Compression (Good)
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

share|improve this question
add comment

1 Answer

Meanwhile I found an algorithm by myself. The first thing I did was the implementation of an algorithm that detects common tails in binary decision diagrams.

The first compression worked by detecting:

(A&B v ~A&false)    --> (A&true v ~A&false)& B  % common tail
(A&B&C v ~A&D&C)    -->     (A&B v ~A&D)& C     % common tail

As a next step I tried a further compression. Instead of detecting common tails, I implemented an algorithm that detects common paths in binary decision diagrams.

The second compression worked by detecting:

(A&B1&C1,..&Bn&Cn v ~A&D1&C1&..&Dn&Cn) -->
    (A&B1&..&Bn v ~A&D1&..&Dn)& C1&..&Cn    % common path

I then did a little benchmark. We used 100’000 randomly picked Boolean functions and computed their compression. We observed an average size reduction of only 2%.

So for evenly distributed Boolean functions it doesn't seem worth it. Maybe if the Boolean functions have already some shape it might give something.

Bye

P.S.: The Prolog source code:
Ordinary Binary Decision Diagrams
http://www.xlog.ch/jekejeke/principia/shannon.p

Compressed Binary Decision Diagrams
http://www.xlog.ch/jekejeke/principia/shannon4.p

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.