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

详细信息    查看全文

• 作者：Igor Chikalov ; Shahid Hussain ; Mikhail Moshkov
• 关键词：Totally optimal decision trees ; monotone Boolean functions ; number of nodes and depth of decision trees
• 刊名：Procedia Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：22
• 期：Complete
• 页码：359-365
• 全文大小：140 K

文摘

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.