JUCS - Journal of Universal Computer Science 3(1): 2-22, doi: 10.3217/jucs-003-01-0002
Bounds on Size of Decision Diagrams
expand article infoVáclav Dvořák
‡ Brno University of Technology, Czech Republic
Open Access
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.