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

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes
1)feb 2024 VRS exam, 1g)
2) and same how to convert representation sets to zdd in 1f) ?
in * TF "Emb. Sys. and Rob." by (120 points)
edited by
I reached here by 1) calculating dnf using truth table 2) converting dnf to rmnf.
After getting set representation of {{a,b,c},{a,c},{b,c},{}} which is rmnf.
How to convert this sets into FDD graph below??
vrs exam , feb 2024, Q1 part g)

1 Answer

0 votes

ZDDs and FDDs make use of the interpretation of decision diagrams as sets of sets. While ZDDs store the full minterms of a DNF as sets of sets, FDDs store the monomials of a RMNF as sets of sets. How a set of set is represented by a decision diagram is explained on slides 140-142 of the BDD chapter of VRS.

For example, consider the following sets of sets {{a,b,c},{a,c},{b,c},{}} that represents the monomials of a Reed-Muller normal form. Converting this into a decision diagram with variable ordering c<b<a works as follows: First, we partition the sets into those containing "a", and those not containing "a":

  • {a,b,c},{a,c} which yield {b,c},{c} for the positive edge
  • {b,c},{} for the negative edge

For the positive edge, we continue with paritioning by "b":

  • {b,c} which yield {c} for the positive edge
  • {c} for the negative edge

So, we get a node labelled with "b" having two edges for the set representation of {c} which is just a node labelled with c having  positive and negative edges to the 1-leaf and 0-leaf, respectively.

For the negative edge of "a", we also continue with paritioning by "b":

  • {b,c} which yield {c} for the positive edge
  • {} for the negative edge

So, we get a node labelled with "b" having a positive edge to the c-node that we already have, and a negative edge to the 1-leaf. Note that the 0-leaf is represented by {} and the 1-leaf is represented by {{}}.

by (170k points)

Related questions

+2 votes
2 answers
asked Aug 7, 2018 in * TF "Emb. Sys. and Rob." by Pavonlo (280 points)
0 votes
1 answer
asked Jan 14 in * TF "Emb. Sys. and Rob." by Faris (180 points)
0 votes
1 answer
+1 vote
2 answers
asked Jul 7, 2020 in # Study-Organisation (Master) by RS (770 points)
Imprint | Privacy Policy
...