Totally Optimal Decision Trees for Monotone Boolean Functions with at Most Five Variables

Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

In this paper, we present the empirical results for relationships between time (depth) and space (number of nodes) complexity of decision trees computing monotone Boolean functions, with at most five variables. We use Dagger (a tool for optimization of decision trees and decision rules) to conduct experiments. We show that, for each monotone Boolean function with at most five variables, there exists a totally optimal decision tree which is optimal with respect to both depth and number of nodes.
Original languageEnglish (US)
Title of host publicationProcedia Computer Science
PublisherElsevier BV
Pages359-365
Number of pages7
DOIs
StatePublished - 2013

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

Fingerprint

Dive into the research topics of 'Totally Optimal Decision Trees for Monotone Boolean Functions with at Most Five Variables'. Together they form a unique fingerprint.

Cite this