Query Learning of Bounded-Width OBDDs
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^3) equivalence queries alone, where n is the number of variables. We also present a learning algorithm for width-2 OBDDs which uses O( n ) proper equivalence queries and O(n^2) 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.
Cite
Text
Nakamura. "Query Learning of Bounded-Width OBDDs." International Conference on Algorithmic Learning Theory, 1996. doi:10.1007/3-540-61863-5_32Markdown
[Nakamura. "Query Learning of Bounded-Width OBDDs." International Conference on Algorithmic Learning Theory, 1996.](https://mlanthology.org/alt/1996/nakamura1996alt-query/) doi:10.1007/3-540-61863-5_32BibTeX
@inproceedings{nakamura1996alt-query,
title = {{Query Learning of Bounded-Width OBDDs}},
author = {Nakamura, Atsuyoshi},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1996},
pages = {37-50},
doi = {10.1007/3-540-61863-5_32},
url = {https://mlanthology.org/alt/1996/nakamura1996alt-query/}
}