DocumentCode :
1554988
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
Volume :
46
Issue :
4
fYear :
1997
fDate :
4/1/1997 12:00:00 AM
Firstpage :
491
Lastpage :
494
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;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.588065
Filename :
588065
Link To Document :
بازگشت