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.
- Decision tree
- Information system
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics