An efficient query learning algorithm for zero-suppressed binary decision diagrams


Hayato Mizumoto, Shota Todoroki, Diptarama, Ryo Yoshinaka, Ayumi Shinohara ;
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:360-371, 2017.


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.

Related Material