Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams |
| |
Authors: | B Bollig I Wegener |
| |
Affiliation: | FB Informatik, LS II, Universit?t Dortmund, 44221 Dortmund, Germany bollig@ls2.informatik.uni-dortmund.de, wegener@ls2.informatik.uni-dortmund.de, DE
|
| |
Abstract: | Ordered binary decision diagrams (OBDDs) have found many applications in the verification of combinational and sequential
circuits, protocols, and the synthesis and analysis of systems. The applications are limited, since the expressive power of
polynomial-size OBDDs is too restricted. Therefore, several more general BDD models are used. Partitioned OBDDs are OBDD models
allowing restricted use of nondeterminism and different variable orderings. They are restricted enough such that the essential
operations can be performed efficiently and they allow polynomial-size representations for many more functions than OBDDs.
Here the expressive power of polynomial-size partitioned OBDDs is investigated. A tight hierarchy with respect to the number
of parts in the partition is proved and partitioned OBDDs are compared with other BDD models.
Received April 1998, and in final form September 1998. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|