Book

Time Complexity of Decision Trees (research monograph)

Time Complexity of Decision Trees (research monograph)

M.Moshkov, ​
Time Complexity of Decision Trees (research monograph), Transactions on Rough Sets III,
Lecture Notes in Computer Science 3400, Springer, 244-459 (2005)

http://www.springerlink.com/content/nvktef8bdbtyb4fc/

The research monograph is devoted to the study of bounds on time complexity in the worst case of decision trees and algorithms for decision tree construction. The monograph is organized in four parts. In the first part (Sects. 1 and 2) results of the monograph are discussed in context of rough set theory and decision tree theory. In the second part (Sect. 3) some tools for decision tree investigation based on the notion of decision table are described. In the third part (Sects. 4–6) general results about time complexity of decision trees over arbitrary (finite and infinite) information systems are considered. The fourth part (Sects. 7–11) contains a collection of mathematical results on decision trees in areas of rough set theory and decision tree theory applications such as discrete optimization, analysis of acyclic programs, pattern recognition, fault diagnosis and probabilistic reasoning.