Average and Worst Case Number of Nodes in Decision Diagrams of Symmetric Multiple-Valued Functions
Abstract
We derive the average and worst case number of nodes in decision diagrams of r-valued symmetric functions of n variables. We show that, for large n, both numbers approach n(r)/r. For binary decision diagrams (r = 2 ), we compute the distribution of the number of functions on n variables with a specified number of nodes. Subclasses of symmetric functions appear as features in this distribution. For example, voting functions are noted as having an average of n(2)/6 nodes, for large n, compared to n(2)/2 , for general binary symmetric functions.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1997
- Accession Number
- ADA605508
Entities
People
- Jon T. Butler
- Robert J. Barton Iii
- Tsutomu Sasao
Organizations
- Naval Postgraduate School