Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T19:05:15.226Z Has data issue: false hasContentIssue false

On the Complexity of the Hidden Weighted Bit Function for Various BDD Models

Published online by Cambridge University Press:  15 August 2002

Beate Bollig
Affiliation:
FB Informatik, LS 2, Univ. Dortmund, 44221 Dortmund, Germany.
Martin Löbbing
Affiliation:
FB Informatik, LS 2, Univ. Dortmund, 44221 Dortmund, Germany.
Martin Sauerhoff
Affiliation:
FB Informatik, LS 2, Univ. Dortmund, 44221 Dortmund, Germany.
Ingo Wegener
Affiliation:
FB Informatik, LS 2, Univ. Dortmund, 44221 Dortmund, Germany.
Get access

Abstract

Ordered binary decision diagrams (OBDDs) and several more general BDD models have turned out to be representations of Boolean functions which are useful in applications like verification, timing analysis, test pattern generation or combinatorial optimization.The hidden weighted bit function (HWB) is of particular interest, since it seems to be the simplest function with exponential OBDD size. The complexity of this function with respect to different circuit models, formulas, and various BDD models is discussed.

Information

Type
Research Article
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable