Classification of infinite information systems depending on complexity of decision trees and decision rule systems

Mikhail Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

In this paper, infinite information systems used in pattern recognition, data mining, discrete optimization, and computational geometry are investigated. Time and space complexity of decision trees and complete decision rule systems are studied. A partition of the set of all infinite information systems into two classes is considered. Information systems from the first class are close to the best from the point of view of time and space complexity of decision trees and decision rule systems. Decision trees and decision rule systems for information systems from the second class have in the worst case large time or space complexity.

Original languageEnglish (US)
Pages (from-to)345-368
Number of pages24
JournalFundamenta Informaticae
Volume54
Issue number4
StatePublished - Mar 1 2003

Keywords

  • Decision rule systems
  • Decision trees
  • Space complexity
  • 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 'Classification of infinite information systems depending on complexity of decision trees and decision rule systems'. Together they form a unique fingerprint.

Cite this