Query Learning Algorithm for Ordered Multi-Terminal Binary Decision Diagrams
This work provides an incremental extension of query learning algorithms to OMTBDDs, potentially benefiting researchers in formal verification and machine learning classification tasks.
The authors developed a query learning algorithm for ordered multi-terminal binary decision diagrams (OMTBDDs) that requires at most n equivalence and 2n(⌈log₂ m⌉ + 3n) membership queries, extending existing OBDD methods. They validated the tightness of these bounds with synthetic OMTBDDs and demonstrated potential applications in classification using UCI datasets.
We propose a query learning algorithm for ordered multi-terminal binary decision diagrams (OMTBDDs) using at most n equivalence and 2n(l\lcei\log_2 m\rceil+ 3n) membership queries by extending the algorithm for ordered binary decision diagrams (OBDDs). Tightness of our upper bounds is checked in our experiments using synthetically generated target OMTBDDs. Possibility of applying our algorithm to classification problems is also indicated in our other experiments using datasets of UCI Machine Learning Repository.