Miao Chen

Defense Date

4-8-2005

Graduation Date

2005

Availability

Immediate Access

Submission Type

thesis

Degree Name

MS

Department

Computational Mathematics

School

McAnulty College and Graduate School of Liberal Arts

Committee Chair

Jeffrey Jackson

Committee Member

Donald L. Simon

Committee Member

Patrick Juola

Keywords

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

Abstract

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.

Format

PDF

Language

English

Download

Share

COinS