In Knuth's analysis on ZDDs and BDDs he states that for a given boolean function f the bounds of the size difference are:
$ZDD\_size(f) \leq n/2 (BDD\_size(f) + 1) + 1$
$BDD\_size(f) \leq n/2 (ZDD\_size(f) + 1) + 2$
I am investigating the XOR pattern (where only one of the variables of a given set is true) for which i was wondering whether the ZDD representation has the most possible improvement over the BDD version; no nodes are eliminated with the BDD rule and if i would change the pattern such that more nodes can be eliminated with the ZDD rule, then there would equal or more nodes eliminated by the BDD rule. Yet, when i build a ZDD and BDD for such a XOR pattern for lets say 6 variables, i get that the BDD size is 21 and the ZDD size is 6. This is close to the maximum distance described by Knuth but not completely (by a constant of 2 for any number of variables)...
I cannot find literature describing this pattern for maximum difference and i cannot immediately proof this idea either. Therefore i want to ask if you guys know any literature on this, or the proof itself, or help me with how i should approach proving this. Very maybe it could be that the max advantage of ZDD size over BDD size given by Knuth should be reduced by 2?
Many thanks!
See 7.1.4 page 250/ 251 Knuth, Donald E., The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1., Upper Saddle River, NJ: Addison-Wesley (ISBN 978-0-201-03804-0/pbk). xv, 883 p. (2011). ZBL1354.68001.