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


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
Number of pages12
StatePublished - 2020

Publication series

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

Bibliographical note

Publisher Copyright:
© 2020, The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG.

ASJC Scopus subject areas

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


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