AVERAGE AND WORST-CASE NUMBER OF NODES IN DECISION DIAGRAMS OF SYMMETRICAL MULTIPLE-VALUED FUNCTIONS

We derive the average and worst case number of nodes in decision diagr ams of r-valued symmetric functions of n variables. We show that, for large n, both numbers approach nr/rl. For binary decision diagrams (r = 2), we compute the distribution of the number of functions on n vari ables with a specified number of nodes. Subclasses of symmetric functi ons appear as features in this distribution. For example, voting funct ions are noted as having an average of n2/6 nodes, for large n, compar ed to n2/2, for general binary symmetric functions.