Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


546 users

0 votes
exercise sheet 3 question 2.b:

would you please give a hint how it works? I read a lot but couldn't understand how to solve this problem!!!
in * TF "Emb. Sys. and Rob." by (1.7k points)

1 Answer

0 votes
Best answer

So you are looking for hints on how to convert a ZDD to Reed-Muller-Normal-Form. There you go:

  1. Use Davio-Decomposition to build a FDD and read the RMNF from that.
  2. Non-overlapping-DNF-to-RMNF:
The Non-overlapping-DNF-to-RMNF conversion works like this:
  1. Read the DNF from the ZDD/ROBDD
  2. Make sure that the DNF is non-overlapping (e.g. containing no pair of co-clauses that can be satisfied by the same assignment)
  3. Since the co-clauses don't overlap, you the disjunctions are here the same as excluseive-or. Hence, replace all the OR by XOR.
  4. Now the formula consists of XOR, conjunction, and negation. RMNF doesn't allow negation. Replace ¬X by (1 XOR x)
  5. Multiply the inner XOR-terms out.
by (25.6k points)
selected by

Related questions

Imprint | Privacy Policy