Butler, J.T.J.T.ButlerHerscovici, D.S.D.S.HerscoviciSasao, T.T.SasaoBarton, R.J.R.J.Barton2022-03-032022-03-031997https://publica.fraunhofer.de/handle/publica/18995410.1109/12.588065We 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.enAsymptotic ApproximationAverage-CaseBDDcomplexityDecision DiagramsMultiple-Valued FunctionsSymmetric Functions006400Average and Worst Case Number of Nodes in Decision Diagrams of Symmetric Multiple-Valued Functionsjournal article