An Efficient Exact Learning Algorithm for Ordered Binary Decision Diagrams
Abstract
In this paper, we propose a new algorithm which exactly learns ordered binary decision diagrams (OBDDs) with a given variable ordering via equivalence queries and membership queries. Our algorithm uses at most n equivalence queries and at most 2 n ([log_2 m ] + 3 n ) membership queries, where n is the number of nodes in the target reduced OBDD and m is the number of variables. We have reduced the number of membership queries by a factor of m compared with the best known algorithm for this problem due to Gavaldà and Guijarro.
Cite
Text
Nakamura. "An Efficient Exact Learning Algorithm for Ordered Binary Decision Diagrams." International Conference on Algorithmic Learning Theory, 1997. doi:10.1007/3-540-63577-7_51Markdown
[Nakamura. "An Efficient Exact Learning Algorithm for Ordered Binary Decision Diagrams." International Conference on Algorithmic Learning Theory, 1997.](https://mlanthology.org/alt/1997/nakamura1997alt-efficient/) doi:10.1007/3-540-63577-7_51BibTeX
@inproceedings{nakamura1997alt-efficient,
title = {{An Efficient Exact Learning Algorithm for Ordered Binary Decision Diagrams}},
author = {Nakamura, Atsuyoshi},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1997},
pages = {307-322},
doi = {10.1007/3-540-63577-7_51},
url = {https://mlanthology.org/alt/1997/nakamura1997alt-efficient/}
}