Time complexity of decision trees

Mikhail Ju Moshkov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

50 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationTransactions on Rough Sets III
PublisherSpringer Verlag
Pages244-259
Number of pages16
ISBN (Print)3540259988, 9783540259985
DOIs
StatePublished - Jan 1 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3400 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Decision tree
  • Rough set theory
  • Test theory
  • Time complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this