Accession Number:

ADA605508

Title:

Average and Worst Case Number of Nodes in Decision Diagrams of Symmetric Multiple-Valued Functions

Descriptive Note:

Journal article

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Report Date:

1997-04-01

Pagination or Media Count:

0.0

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 nrr. 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 n26 nodes, for large n, compared to n22 , for general binary symmetric functions.

Subject Categories:

  • Administration and Management
  • Theoretical Mathematics
  • Printing and Graphic Arts

Distribution Statement:

APPROVED FOR PUBLIC RELEASE