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.

## Abstract

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