Abstract
This paper contains some results concerning the properties of decision trees with minimal average depth. The sufficient conditions, which allows for performing a decomposition of problem are given. The class of all information systems, which have linear upper bounds on minimal average weighted depth depending only on entropy, is described. The exponential lower bounds on the number of vertices in branching programs with minimal average weighted depth for some problems are obtained.
Get full access to this article
View all access options for this article.