Bounds on Size of Decision Diagrams

Václav Dvořák (Technical University Brno, Czech Republic)

Abstract: Known upper bounds on the number of required nodes (size) in the ordered binary and multiple-valued decision diagram (DD) for representation of logic functions are reviewed and reduced by a small constant factor. New upper bounds are derived for partial logic functions containing don t cares and also for complete Boolean functions specified by Boolean expressions. The evaluation of upper bounds is based on a bottom-up algorithm for constructing efficient ordered DDs developed by the author.

Categories: B.5.2, B.6, K.8.2