Unimprovable upper bounds on time complexity of decision trees

Mikhail Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

The paper is devoted to investigation of behavior of global Shannon functions which produce unimprovable upper bounds on time complexity of decision trees over arbitrary information systems.

Original languageEnglish (US)
Pages (from-to)157-184
Number of pages28
JournalFundamenta Informaticae
Volume31
Issue number2
DOIs
StatePublished - Aug 1997

Keywords

  • Decision tree
  • Information system
  • Time complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Unimprovable upper bounds on time complexity of decision trees'. Together they form a unique fingerprint.

Cite this