On Average Depth of Decision Trees Implementing Boolean Functions

Article type: Research Article

Authors: Chikalov, Igor

Affiliations: Faculty of Computing Mathematics and Cybernetics, Nizhny Novgorod State University, 23, Gagarina Av., Nizhny Novgorod, 603950, Russia

Abstract: The article considers the representation of Boolean functions in the form of decision trees. It presents the bounds on average time complexity of decision trees for all classes of Boolean functions that are closed over substitution, and the insertion and deletion of unessential variables (the structure of these classes is described in the book by Jablonsky, Gavrilov and Kudriavtzev [5]. The obtained results are compared with the results developed by Moshkov in [6] that describe the worst case time complexity of decision trees.

Keywords: boolean function, decision tree, average time complexity

Journal: Fundamenta Informaticae, vol. 50, no. 3-4, pp. 265-284, 2002