Lower Bounds on Complexity of Deterministic Decision Trees for Decision Tables

Mikhail Moshkov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

Abstract

In this chapter, lower bounds on complexity of deterministic decision trees for decision tables are studied that are based on the notions of super-cover, super-partition, test, and system of representatives for decision tables. An approach to the proof of lower bounds is also considered which is based on the use of so-called proof-trees.

Original languageEnglish (US)
Title of host publicationIntelligent Systems Reference Library
PublisherSpringer
Pages25-36
Number of pages12
DOIs
StatePublished - 2020

Publication series

NameIntelligent Systems Reference Library
Volume179
ISSN (Print)1868-4394
ISSN (Electronic)1868-4408

ASJC Scopus subject areas

  • Computer Science(all)
  • Information Systems and Management
  • Library and Information Sciences

Fingerprint

Dive into the research topics of 'Lower Bounds on Complexity of Deterministic Decision Trees for Decision Tables'. Together they form a unique fingerprint.

Cite this