On the class of restricted linear information systems

Mikhail Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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
Issue number22
StatePublished - Oct 28 2007


  • Complexity
  • Decision tree
  • Information system
  • Optimization

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Cite this