An efficient query learning algorithm for zero-suppressed binary decision diagrams
International Conference on Algorithmic Learning Theory (ALT2017),
Proceedings of Machine Learning Research Vol.76, pp.360-371
(2017), [peer-reviewed]
Event Date:
October 15-17, 2017
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(⌊logm⌋+4n)$ membership queries to learn the target ZDD.