The I/O-Complexity of Ordered Binary-Decision Diagram Manipulation
AbstractOrdered Binary-Decision Diagrams (OBDD) are the state-of-the art
data structure for boolean function manipulation and there exist
several software packages for OBDD manipulation. OBDDs have
been successfully used to solve problems in e.g. digital-systems design, verification and testing, in mathematical logic, concurrent system design and in artificial intelligence. The OBDDs used in many of these applications quickly get larger than the available main memory and it becomes essential to consider the problem of minimizing the Input/Output (I/O) communication. In this paper we analyze why existing OBDD manipulation algorithms perform poorly in an I/O environment and develop new I/O-efficient algorithms.
How to Cite
Arge, L. (1996). The I/O-Complexity of Ordered Binary-Decision Diagram Manipulation. BRICS Report Series, 3(29). https://doi.org/10.7146/brics.v3i29.20010
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.