Repository: Freie Universität Berlin, Math Department

Ordered binary decision diagrams and the Shannon effect

Gröpl, C. and Prömel, H.-J. and Srivastav, A. (2004) Ordered binary decision diagrams and the Shannon effect. Discrete Applied Mathematics, 142 . pp. 67-85.

Full text not available from this repository.


We investigate the size and structure of ordered binary decision diagrams (OBDDs) for random Boolean functions. It was known that for most values of n, the expected OBDD size of a random Boolean function with n variables is equal to the worst-case size up to terms of lower order. Such a phenomenon is generally called strong Shannon effect. Here we show that the strong Shannon effect is not valid for all n. Instead it undergoes a certain periodic `phase transition': If n lies within intervals of constant width around the values n = 2h + h, then the strong Shannon effect does not hold, whereas it does hold outside these intervals. Our analysis provides doubly exponential probability bounds and generalises to ordered Kronecker functional decision diagrams (OKFDDs).

Item Type:Article
Uncontrolled Keywords:VLSI-Design and layout, Binary Decision Diagrams, Graph theory (other), Hardware verification, Probability theory, Random graphs, Randomized algorithms and probabilistic analysis, Theoretical computer science (other)
Subjects:Mathematical and Computer Sciences > Computer Science
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:360
Deposited By: Admin Administrator
Deposited On:14 Apr 2009 14:35
Last Modified:14 Apr 2009 14:35

Repository Staff Only: item control page