On the class of restricted linear information systems

Mikhail Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

In the paper the class of restricted linear information systems is described completely. For decision tables over each such information system there exist low upper bounds on minimal complexity of decision trees and polynomial algorithms of decision tree optimization for various complexity measures. A corollary connected with combinatorial geometry is considered.

Original languageEnglish (US)
Pages (from-to)2837-2844
Number of pages8
JournalDiscrete Mathematics
Volume307
Issue number22
DOIs
StatePublished - Oct 28 2007

Keywords

  • Complexity
  • Decision tree
  • Information system
  • Optimization

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'On the class of restricted linear information systems'. Together they form a unique fingerprint.

Cite this