Name
Abstract | ||
|---|---|---|
This paper investigates reduced ordered binary decision diagrams (OBDD) of partially symmetric Boolean functions when using variable orders where symmetric variables are adjacent. We prove upper bounds for the size of such symmetry ordered OBDDs (SymOBDD). They generalize the upper bounds for the size of OBDDs of totally symmetric Boolean functions and nonsymmetric Boolean functions proven by Heap and Mercer [14], [15] and Wegener [37]. Experimental results based on these upper bounds show that the nontrivial symmetry sets of a Boolean function should be located either right up at the beginning or right up at the end of the variable order in order to obtain best upper bounds. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/12.844348 | IEEE Trans. Computers |
Keywords | Field | DocType |
boolean function,binary decision diagram,upper bounds,nontrivial symmetry set,symmetric variable,nonsymmetric boolean function,variable order,symmetry properties,upper bound,symmetric boolean function,boolean functions,data structures | Boolean function,Data structure,Discrete mathematics,Combinatorics,Upper and lower bounds,Binary decision diagram,Heap (data structure),Mathematics | Journal |
Volume | Issue | ISSN |
49 | 4 | 0018-9340 |
Citations | PageRank | References |
10 | 0.69 | 23 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laura Heinrich-Litan | 1 | 22 | 2.87 |
| P. Molitor | 2 | 211 | 18.50 |