• English
  • Deutsch
  • Log In
    Password Login
    Research Outputs
    Fundings & Projects
    Researchers
    Institutes
    Statistics
Repository logo
Fraunhofer-Gesellschaft
  1. Home
  2. Fraunhofer-Gesellschaft
  3. Artikel
  4. Average and Worst Case Number of Nodes in Decision Diagrams of Symmetric Multiple-Valued Functions
 
  • Details
  • Full
Options
1997
Journal Article
Title

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 involution 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 squared/6) nodes, for large n, compared to (N sqaured/2), for general binary symmetric functions.
Author(s)
Butler, J.T.
Herscovici, D.S.
Sasao, T.
Barton, R.J.
Journal
IEEE transactions on computers  
Open Access
DOI
10.1109/12.588065
Language
English
Fraunhofer-Institut für Graphische Datenverarbeitung IGD  
Keyword(s)
  • Asymptotic Approximation

  • Average-Case

  • BDD

  • complexity

  • Decision Diagrams

  • Multiple-Valued Functions

  • Symmetric Functions

  • Cookie settings
  • Imprint
  • Privacy policy
  • Api
  • Contact
© 2024