An efficient query learning algorithm for ordered binary decision diagrams. (English) Zbl 1088.68153
Summary: 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 (\lceil \log_{2} m\rceil + 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à and D. Guijarro [“Learning ordered binary decision diagrams”, in: Proc. 6th Int. Workshop on Algorithmic Learning Theory, 228–238 (1995)].
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
References:
| [1] | Angluin, D., Learning regular sets from queries and counterexamples, Information and Computation, 75, 87-106 (1987) · Zbl 0636.68112 |
| [2] | Bryant, R., Symbolic boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys, 24, 3, 293-318 (1992) |
| [3] | F. Bergadano, N. Bshouty, C. Tamon, S. Varricchio, On learning branching programs and small circuits, in: Proceedings of the 3rd European Conference on Computational Learning Theory, Lecture Notes in Artificial Intelligence, vol. 1208, 1997, pp. 150-161.; F. Bergadano, N. Bshouty, C. Tamon, S. Varricchio, On learning branching programs and small circuits, in: Proceedings of the 3rd European Conference on Computational Learning Theory, Lecture Notes in Artificial Intelligence, vol. 1208, 1997, pp. 150-161. |
| [4] | Birkendorf, A.; Simon, H., Using computational learning strategies as a tool for combinatorial optimization, Annals of Mathematics and Artificial Intelligence, 22, 237-257 (1998) · Zbl 0905.68114 |
| [5] | N. Bshouty, C. Tamon, D. Wilson, On learning width two branching programs, in: Proceedings of the 9th Annual Conference on Computational Learning Theory, 1996, pp. 224-227.; N. Bshouty, C. Tamon, D. Wilson, On learning width two branching programs, in: Proceedings of the 9th Annual Conference on Computational Learning Theory, 1996, pp. 224-227. · Zbl 1339.68129 |
| [6] | J.R. Burch, E.M. Clarke, K. McMillan, Symbolic model checking: \(10^{20}\); J.R. Burch, E.M. Clarke, K. McMillan, Symbolic model checking: \(10^{20}\) |
| [7] | F. Ergün, S. Kumar, R. Rubinfeld, On learning bounded-width branching programs, in: Proceedings of the 9th Annual Conference on Computational Learning Theory, 1995, pp. 361-368.; F. Ergün, S. Kumar, R. Rubinfeld, On learning bounded-width branching programs, in: Proceedings of the 9th Annual Conference on Computational Learning Theory, 1995, pp. 361-368. |
| [8] | R. Gavaldà, D. Guijarro, Learning ordered binary decision diagrams, in: Proceedings of the 6th International Workshop on Algorithmic Learning Theory, 1995, pp. 228-238.; R. Gavaldà, D. Guijarro, Learning ordered binary decision diagrams, in: Proceedings of the 6th International Workshop on Algorithmic Learning Theory, 1995, pp. 228-238. · Zbl 1527.68105 |
| [9] | S.-W. Jeong, F. Somenzi, A new algorithm for the binate covering problem and its application to the minimization of Boolean relations, in: Proceedings of IEEE International Conference on Computer-Aided Design (ICCAD-92), 1992, pp. 417-420.; S.-W. Jeong, F. Somenzi, A new algorithm for the binate covering problem and its application to the minimization of Boolean relations, in: Proceedings of IEEE International Conference on Computer-Aided Design (ICCAD-92), 1992, pp. 417-420. |
| [10] | Kearns, M.; Vazirani, U., An Introduction to Computational Learning Theory (1994), The MIT Press: The MIT Press Cambridge, MA |
| [11] | J.C. Madre, J.P. Billon, Proving circuit correctness using formal comparison between expected and extracted behavior, in: Proceedings of the 25th ACM/IEEE Design Automation Conference, 1988, pp.205-210.; J.C. Madre, J.P. Billon, Proving circuit correctness using formal comparison between expected and extracted behavior, in: Proceedings of the 25th ACM/IEEE Design Automation Conference, 1988, pp.205-210. |
| [12] | J.C. Madre, O. Coudert, A logically complete reasoning maintenance system based on a logical constraint solver, in: Proceedings of the 12th International Joint Conference on Artificial Intelligence, 1988, pp. 94-299.; J.C. Madre, O. Coudert, A logically complete reasoning maintenance system based on a logical constraint solver, in: Proceedings of the 12th International Joint Conference on Artificial Intelligence, 1988, pp. 94-299. · Zbl 0747.68072 |
| [13] | Nakamura, A., Query learning of bounded-width OBDDs, Theoretical Computer Science, 241, 83-114 (2000) · Zbl 0944.68157 |
| [14] | Rivest, R.; Schapire, R., Inference of finite automata using homing sequences, Information and Computation, 103, 299-347 (1993) · Zbl 0786.68082 |
| [15] | V. Raghavan, D. Wilkins, Learning \(μ\); V. Raghavan, D. Wilkins, Learning \(μ\) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
