On Polynomial time Constructions of Minimum Height Decision Tree

Nader H. Bshouty, Waseem Makhoul

In this paper we study a polynomial time algorithms that for an input $A\subseteq B_m$ outputs a decision tree for $A$ of minimum depth. This problem has many applications that i…