Title :
Average and worst case number of nodes in decision diagrams of symmetric multiple-valued functions
Author :
Butler, Jon T. ; Herscovici, David S. ; Sasao, Tsutomu ; Barton, Robert J.
Author_Institution :
Dept. of Electr. & Comput. Eng., Naval Postgraduate Sch., Monterey, CA, USA
fDate :
4/1/1997 12:00:00 AM
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 nr/rl. 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 n2/6 nodes, for large n, compared to n2/2, for general binary symmetric functions
Keywords :
computational complexity; decision theory; multivalued logic; binary decision diagrams; decision diagrams; r-valued symmetric functions; symmetric multiple-valued functions; voting functions; Binary decision diagrams; Boolean functions; Computer aided software engineering; Data structures; Distributed computing; Very large scale integration; Voting;
Journal_Title :
Computers, IEEE Transactions on