Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Average and Worst Case Number of Nodes in Decision Diagrams of Symmetric MultipleValued Functions
 IEEE transactions on computers 46 (1997), No.4, pp.491494 ISSN: 00189340 

 English 
 Journal Article 
 Fraunhofer IGD () 
 Asymptotic Approximation; AverageCase; BDD; complexity; Decision Diagrams; MultipleValued Functions; Symmetric Functions 
Abstract
We derive the average and worst case number of nodes in decision diagrams of rvalued 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.