Comparitive analysis of deterministic and nondeterministic decision tree complexity. Global approach

Mikhail Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

We study the relationships between the complexity of a task description and the minimal complexity of deterministic and nondeterministic decision trees solving this task. We investigate decision trees assuming a global approach i.e. arbitrary checks from a given check system can be used for constructing decision trees.

Original languageEnglish (US)
Pages (from-to)201-214
Number of pages14
JournalFundamenta Informaticae
Volume25
Issue number2
StatePublished - Feb 1996
Externally publishedYes

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Comparitive analysis of deterministic and nondeterministic decision tree complexity. Global approach'. Together they form a unique fingerprint.

Cite this