exercise sheet 3 question 3.b

Question

I don't know why my answer to this question is wrong!

here is my solution:

Answer 1

There are already a couple of answers that should clarify the situation. Anyway, let's summarized: You were given the following decision diagram:

It may be a FDD or a ZDD, but for sure it is not a BDD since there a node labelled with a that has the same cofactors which is impossible for BDDs. The exercise question says that you should first compute the set representation which is the same for FDDs and ZDDs, and you have done that correctly and obtained 

    {{a,c},{a},{b},{}}

Looking again at the exercise sheet, you should interpret this decision diagram now as a FDD and should this way derive the represented formula. To make it simple, you should represent the formula in RMF. Your formula is therefore the following one

    a&c ⊕ a ⊕ b ⊕ true

Now you should convert this formula to a ZDD. You will find the following result:

It is the same formula, but given now as a ZDD instead of a FDD. Again, you should derive the set representation of this decision diagram which is now

    {{a,b},{a,c},{c},{}}.

Does this help?

Answer 2

Is your graph right?

Comments

the graph is the one in the question and I didn't change it! shouldn't we use the same graph from question 3.a? because FDD and ZDD represent the same graph.

---

Syntactically, ZDD and FDD are the same class of graphs. Or in other words: If you have a graph, you need to be told whether to interpret it as a ZDD or an FDD. A graph read as an FDD typically represents a different formula than the same graph read as a ZDD.

In question a), you see a FDD representing a formula phi, in task b) you are asked to give the set representation of a ZDD that represents the same formula.

Answer 3

Thank you for your question. A little side note: It would be easier, if you could paraphrase the task.

In part a) of the mentioned task, an FDD for a formula phi is given, and a RMNF formula equivalent to phi is asked for.

In part b), you are asked to give the set representation of a ZDD representing phi (and/or the equivalent formula from task a)).

Apparently, you already constructed the ZDD. As far as I can tell, your set representation correctly represents your ZDD. Maybe, there was a mistake when representing the RMNF as a ZDD.

Answer 4

In exercise sheet 3, question 3, you are given a FDD and asked to first construct a propositional formula in RMNF and then asked to find the the set representation of the ZDD for ϕ. 

So the answer above is the correct set representation for the given FDD. 

But your answer maybe wrong because you are asked to find the set representation of the ZDD for the propositional formula ϕ. So maybe you made a mistake over there.

Comments

so it seems I'm confused between ZDD and FDD. would you please explain how I can find the set representation of ZDD given a FDD? What are the steps? (I just went through the materials again but couldn't find anything that helps me).
Thank you very much.

---

In a) you computed a formula equivalent to phi. Convert that one to ZDD. Done. Converting a formula to ZDD is almost the same as converting it to ROBDD. You can either use the SNF or the Apply-Algorithm. The only difference is that in ZDDs, you are not deleting nodes with double edges but nodes with a high-edge going to zero.