Totally optimal decision trees for Boolean functions

Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

We study decision trees which are totally optimal relative to different sets of complexity parameters for Boolean functions. A totally optimal tree is an optimal tree relative to each parameter from the set simultaneously. We consider the parameters characterizing both time (in the worst- and average-case) and space complexity of decision trees, i.e., depth, total path length (average depth), and number of nodes. We have created tools based on extensions of dynamic programming to study totally optimal trees. These tools are applicable to both exact and approximate decision trees, and allow us to make multi-stage optimization of decision trees relative to different parameters and to count the number of optimal trees. Based on the experimental results we have formulated the following hypotheses (and subsequently proved): for almost all Boolean functions there exist totally optimal decision trees (i) relative to the depth and number of nodes, and (ii) relative to the depth and average depth.
Original languageEnglish (US)
Pages (from-to)1-13
Number of pages13
JournalDiscrete Applied Mathematics
Volume215
DOIs
StatePublished - Jul 28 2016

Fingerprint Dive into the research topics of 'Totally optimal decision trees for Boolean functions'. Together they form a unique fingerprint.

Cite this