Open AccessThe I/O-Complexity of Ordered Binary-Decision Diagram Manipulation
Author(s) -
Lars Arge
Publication year - 1996
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v3i29.20010
Subject(s) - binary decision diagram , boolean function , computer science , theoretical computer science , binary number , boolean algebra , algorithm , mathematics , arithmetic
Ordered 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.