On the size of (generalized) OBDDs for threshold functions |
| |
Authors: | Beate Bollig |
| |
Affiliation: | LS2 Informatik, TU Dortmund, 44221 Dortmund, Germany |
| |
Abstract: | Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Among the many areas of application are hardware verification, model checking, and symbolic graph algorithms. Threshold functions are the basic functions for discrete neural networks and are used as building blocks in the design of some symbolic graph algorithms. In this paper the first exponential lower bound on the size of a more general model than OBDDs and the first nontrivial asymptotically optimal bound on the OBDD size for a threshold function are presented. |
| |
Keywords: | Branching programs Computational complexity Ordered binary decision diagrams Threshold functions |
本文献已被 ScienceDirect 等数据库收录! |