Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 3 / Issue 1

available in:   PDF (102 kB) PS (89 kB)
Similar Docs BibTeX   Write a comment
Links into Future


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