Size and variable ordering of OBDDs representing threshold functions (Q4364580)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1088264
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Size and variable ordering of OBDDs representing threshold functions |
scientific article; zbMATH DE number 1088264 |
Statements
4 November 1998
0 references
Boolean function
0 references
graph representation
0 references
ordered binary decision diagrams
0 references
threshold functions
0 references
lower bound
0 references
0.95207941532135
0 references
0.9432905316352844
0 references
0.9247826337814332
0 references
0.905270218849182
0 references
0.8551878929138184
0 references
Size and variable ordering of OBDDs representing threshold functions (English)
0 references
The size of ordered binary decision diagrams (OBBDs) representing threshold functions is discussed. The lower bound on the OBBD size necessary to represent any threshold function when the variable ordering can be chosen adaptively to minimize the OBBD size is proved. It is shown, that it is not possible to find a good variable ordering only from the total order of weights, that is, for any variable ordering of this kind, there exists a threshold function that requires an exponential size OBBD, but is represented in polynomial size by the optimal ordering. For the entire collection see [Zbl 0869.00027].
0 references
