On Average Depth of Decision Trees Implementing Boolean Functions

• Autorzy: Chikalov I.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Boolean function; decision tree; averaging time

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 50, nr 3,4
• Strony: 265--284
• Opis fizyczny: bibliogr. 9 poz.

Twórcy

autor

Chikalov I.

• Faculty of Computing Mathematics and Cybernetics of Nizhni Novgorod State University, 23, Gagarina Av., Nizhni Novgorod, 603950, Russia,