McAnulty College and Graduate School of Liberal Arts
Donald L. Simon
disjunctive normal form, influence, monotone Boolean decision tree, monotone Boolean function, optimal tree construction, optimal tree size
This thesis focuses on finding counterexamples for the conjecture suggested by Dr. Jackson that if two Boolean variables i and j in a monotone Boolean function have the relation such that if i is relevant in only one sub-tree with j as root while j is relevant in both sub-trees with i as root, then the optimal tree size (defined as the number of leaves in the tree) with j as root is as least as small as the optimal tree size with i as root. All distinct monotone Boolean functions of up to 6 variables and some interesting functions of 7 and 8 variables are tested; no counterexample has been found.
Chen, M. (2005). Towards Optimal Tree Construction of Monotone Functions (Master's thesis, Duquesne University). Retrieved from https://dsc.duq.edu/etd/396