Variable orderings and the size of OBDDs for random partially symmetric Boolean functions
✍ Scribed by Detlef Sieling
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 268 KB
- Volume
- 13
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
The size of ordered binary decision diagrams OBDDs strongly depends on the chosen variable ordering. It is an obvious heuristic to use symmetric variable orderings, i.e., variable orderings where symmetric variables are arranged adjacently. In order to evaluate this heuristic, methods for estimating the OBDD size for random partially symmetric functions are presented. Characterizations of cases where, with high probability, only symmetric variable orderings and, with high probability, only nonsymmetric variable orderings lead to minimum OBDD size are obtained. For this analysis estimates for the number of different blocks of random Boolean matrices are used.