Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10330952 | Information and Computation | 2005 | 21 Pages |
Abstract
In this paper, we propose a new algorithm that exactly learns ordered binary decision diagrams (OBDDs) with a given variable ordering via equivalence and membership queries. Our algorithm uses at most n equivalence queries and at most 2n (âlog2 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. Gavaldà , D. Guijarro, Learning Ordered Binary Decision Diagrams, Proceedings of the 6th International Workshop on Algorithmic Learning Theory, 1995, pp. 228-238].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Atsuyoshi Nakamura,