TY - GEN
T1 - Totally Optimal Decision Trees for Monotone Boolean Functions with at Most Five Variables
AU - Chikalov, Igor
AU - Hussain, Shahid
AU - Moshkov, Mikhail
N1 - KAUST Repository Item: Exported on 2020-10-01
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://hdl.handle.net/10754/552479
UR - http://linkinghub.elsevier.com/retrieve/pii/S187705091300906X
UR - http://www.scopus.com/inward/record.url?scp=84896955363&partnerID=8YFLogxK
U2 - 10.1016/j.procs.2013.09.113
DO - 10.1016/j.procs.2013.09.113
M3 - Conference contribution
SP - 359
EP - 365
BT - Procedia Computer Science
PB - Elsevier BV
ER -