Learning Ordered Binary Decision Diagrams
Abstract
This note studies the learnability of ordered binary decision diagrams (obdds). We give a polynomial-time algorithm using membership and equivalence queries that finds the minimum obdd for the target respecting a given ordering. We also prove that both types of queries and the restriction to a given ordering are necessary if we want minimality in the output, unless P=NP. If learning has to occur with respect to the optimal variable ordering, polynomial-time learnability implies the approximability of two NP-hard optimization problems: the problem of finding the optimal variable ordering for a given obdd and the Optimal Linear Arrangement problem on graphs.
Cite
Text
Gavaldà and Guijarro. "Learning Ordered Binary Decision Diagrams." International Conference on Algorithmic Learning Theory, 1995. doi:10.1007/3-540-60454-5_41Markdown
[Gavaldà and Guijarro. "Learning Ordered Binary Decision Diagrams." International Conference on Algorithmic Learning Theory, 1995.](https://mlanthology.org/alt/1995/gavalda1995alt-learning/) doi:10.1007/3-540-60454-5_41BibTeX
@inproceedings{gavalda1995alt-learning,
title = {{Learning Ordered Binary Decision Diagrams}},
author = {Gavaldà, Ricard and Guijarro, David},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1995},
pages = {228-238},
doi = {10.1007/3-540-60454-5_41},
url = {https://mlanthology.org/alt/1995/gavalda1995alt-learning/}
}