Closed Classes of Boolean Functions

Mikhail Moshkov*

*Corresponding author for this work

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


In this chapter, for decision tables corresponding to functions from an arbitrary closed class of Boolean functions, the depth of deterministic, nondeterministic, and strongly nondeterministic decision trees is studied. The obtained results have some independent interest. Proofs of these results illustrate mainly methods for the proof of lower bounds on complexity of decision trees.

Original languageEnglish (US)
Title of host publicationIntelligent Systems Reference Library
Number of pages11
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

  • General Computer Science
  • Information Systems and Management
  • Library and Information Sciences


Dive into the research topics of 'Closed Classes of Boolean Functions'. Together they form a unique fingerprint.

Cite this