Euristica per stimare l'efficienza dei diagrammi delle decisioni binarie ordinate ridotte?

Question

Reduced Ordered Binary Decision Diagrams (ROBDD) sono una struttura dati efficiente per le funzioni booleane di più variabili f(x1,x2,...,xn). Mi piacerebbe avere un'intuizione per come sono efficienti.

Ad esempio, per la compressione dei dati, sappiamo che i dati con bassa entropia (alcuni simboli appaiono più spesso di altri, molte ripetizioni) possono essere compressi molto bene mentre i dati completamente casuali non possono essere compressi.

C'è un'intuizione analoga per stimare quanto efficientemente i ROBDD possano rappresentare una data formula booleana? Qualsiasi letteratura su questo argomento (preferibilmente online)?

Answer 1

C'è della carta nell'articolo di Wikipedia Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams che fornisce i limiti inferiore e superiore per alcune classi di funzioni (simmetriche, che rappresentano l'aritmetica binaria). Penso che nel caso medio 2n*log n >= 2^k resti, dove n è il numero di nodi nel diagramma e k è il numero di variabili della funzione. Il limite superiore è n <= 2^(k+1) - 1 raggiunto con l'albero binario completo.