Deterministic and nondeterministic decision trees for rough computing

Mikhail Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In the paper, infinite information systems are considered which are used in pattern recognition, discrete optimization, computational geometry. Depth and size of deterministic and nondeterministic decision trees over such information systems are studied. Two classes of infinite information systems are investigated. Systems from these classes are best from the point of view of time complexity and space complexity of deterministic as well as nondeterministic decision trees. In proofs methods of test theory [1] and rough set theory [6, 9] are used.

Original languageEnglish (US)
Pages (from-to)301-311
Number of pages11
JournalFundamenta Informaticae
Issue number3
StatePublished - Feb 2000
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics


Dive into the research topics of 'Deterministic and nondeterministic decision trees for rough computing'. Together they form a unique fingerprint.

Cite this