𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Size of ordered binary decision diagrams representing threshold functions

✍ Scribed by K. Hosaka; Y. Takenaga; T. Kaneda; S. Yajima

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
956 KB
Volume
180
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

An ordered binary decision diagram (OBDD) is a graph representation of a Boolean function. In this paper, the size of ordered binary decision diagrams representing threshold functions is discussed. We consider two cases: the case when a variable ordering is given and the case when it is adaptively chosen. We show 1) 0(2"!') upper bound for both cases, 2) R(2"j2) lower bound for the former case and 3) R(n2 &12) lower bound for the latter case. We also show some relations between the variable ordering and the size of OBDDs representing threshold functions.

πŸ“œ SIMILAR VOLUMES

On random orderings of variables for par
On random orderings of variables for parity ordered binary decision diagrams
✍ Petr SavickΓ½ πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 93 KB

## Ordered binary decision diagrams (OBDDs) are a model for representing Boolean functions. There is also a more powerful variant called parity OBDDs. The size of the representation of a given function depends in both these models on the chosen ordering of the variables. It is known that there are