Restricted Linear Information Systems

摘要

In the paper a class of infinite information systems is described. 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.