Towards Optimal Tree Construction of Monotone Functions

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.

Name thesis:degree_name

MS

Level thesis:degree_level

Immediate Access

Discipline thesis:degree_discipline

Computational Mathematics

Year dc:date.available

2005

Author dc:creator

• Chen, Miao

Contributors dc:contributor

• Jeffrey Jackson
• Donald L. Simon
• Patrick Juola

• disjunctive normal form
• influence
• monotone Boolean decision tree
• monotone Boolean function
• optimal tree construction
• optimal tree size

Language dc:language

English

Repository record dc:identifier

https://dsc.duq.edu/etd/396

OAI identifier oai:identifier

oai:dsc.duq.edu:etd-1409