An Efficient Query Learning Algorithm for Zero-Suppressed Binary Decision Diagrams
Abstract
A ZDD is a directed acyclic graph that represents a family of sets over a fixed universe set. In this paper, we propose an algorithm that learns zero-suppressed binary decision diagrams (ZDDs) using membership and equivalence queries. If the target ZDD has $n$ nodes and the cardinality of the universe is $m$, our algorithm uses $n$ equivalence queries and at most $n(\lfloor \log m \rfloor + 4n)$ membership queries to learn the target ZDD.
Cite
Text
Mizumoto et al. "An Efficient Query Learning Algorithm for Zero-Suppressed Binary Decision Diagrams." Proceedings of the 28th International Conference on Algorithmic Learning Theory, 2017.Markdown
[Mizumoto et al. "An Efficient Query Learning Algorithm for Zero-Suppressed Binary Decision Diagrams." Proceedings of the 28th International Conference on Algorithmic Learning Theory, 2017.](https://mlanthology.org/alt/2017/mizumoto2017alt-efficient/)BibTeX
@inproceedings{mizumoto2017alt-efficient,
title = {{An Efficient Query Learning Algorithm for Zero-Suppressed Binary Decision Diagrams}},
author = {Mizumoto, Hayato and Todoroki, Shota and Diptarama, and Yoshinaka, Ryo and Shinohara, Ayumi},
booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory},
year = {2017},
pages = {360-371},
volume = {76},
url = {https://mlanthology.org/alt/2017/mizumoto2017alt-efficient/}
}