Critical Properties and Complexity Measures of Read-Once Boolean Functions

Vadim Lozin, Mikhail Moshkov

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we define a quasi-order on the set of read-once Boolean functions and show that this is a well-quasi-order. This implies that every parameter measuring complexity of the functions can be characterized by a finite set of minimal subclasses of read-once functions, where this parameter is unbounded. We focus on two parameters related to certificate complexity and characterize each of them in the terminology of minimal classes.
Original languageEnglish (US)
JournalAnnals of Mathematics and Artificial Intelligence
DOIs
StatePublished - Mar 22 2021

ASJC Scopus subject areas

  • Artificial Intelligence
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Critical Properties and Complexity Measures of Read-Once Boolean Functions'. Together they form a unique fingerprint.

Cite this