An efficient query learning algorithm for ordered binary decision diagrams

摘要

In this paper, we propose a new algorithm that exactly learns ordered binary decision diagrams (OB-DDs) with a given variable ordering via equivalence and membership queries. Our algorithm uses at most n equivalence queries and at most 2n([log_2 m] + 3n) membership queries, where n is the number of nodes in the target-reduced OBDD and m is the number of variables. The upper bound on the number of membership queries is smaller by a factor of O(m) compared with that for the previous best known algorithm proposed by R. Gavalda and D. Guijarro [Learning Ordered Binary Decision Diagrams, Proceedings of the 6th International Workshop on Algorithmic Learning Theory, 1995, pp. 228-238].