Query learning of bounded-width OBDDs

Author: Atsuyoshi Nakamura
Email: atsu@sbl.cl.nec.co.jp

Source: Theoretical Computer Science Vol. 241, No. 1-2, 2000, 83-114.

Abstract. In this paper, we study exact learnability of bounded-width ordered binary decision diagrams (OBDDs) when no ordering of the variables is given and learning is conducted by way of equivalence queries and membership queries. We present a learning algorithm for width-2 OBDDs, an algorithm which uses O(n³) equivalence queries alone, where n is the number of variables. We also present a learning algorithm for width-2 OBDDs that uses O(n) proper equivalence queries and O(n²) membership queries. Further, we show a negative result: that there are no polynomial-time algorithms capable of learning width-3 OBDDs from proper equivalence queries alone.