Igor Chikalov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Decision trees appeared in 50-60s of the last century in theoretical computer science [14, 64, 80] and applications [24, 37]. Similar objects are also considered by natural and social sciences, for example, taxonomy keys [30] or questionnaires [63]. Decision trees naturally represent identification and testing algorithms that specify the next test to perform based on the results of the previous tests. A number of particular formulations were generalized by Garey [27] as identification problem that is a problem of distinguishing objects described by a common set of attributes. More general formulation is provided by decision table framework [34, 65] where objects can have incomplete set of attributes and non-unique class labels. In that case, acquiring class label is enough to solve the problem: identifying a particular object is not required. In this context, decision trees found many applications in test theory [39, 45, 46, 81], fault diagnosis [14, 60, 72], rough set theory [61, 62], discrete optimization, non-procedural programming languages [34], analysis of algorithm complexity [38], computer vision [74], computational geometry [69]. © Springer-Verlag Berlin Heidelberg 2011.
Original languageEnglish (US)
Pages (from-to)1-14
Number of pages14
JournalAverage Time Complexity of Decision Trees
StatePublished - 2011

ASJC Scopus subject areas

  • Library and Information Sciences
  • General Computer Science
  • Information Systems and Management


Dive into the research topics of 'Introduction'. Together they form a unique fingerprint.

Cite this