Critical Properties and Complexity Measures of Read-Once Boolean Functions

Vadim Lozin; Mikhail Moshkov

doi:10.1007/s10472-021-09734-6

Critical Properties and Complexity Measures of Read-Once Boolean Functions

Research output: Contribution to journal › Article › peer-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 language	English (US)
Journal	Annals of Mathematics and Artificial Intelligence
DOIs	https://doi.org/10.1007/s10472-021-09734-6
State	Published - Mar 22 2021

Bibliographical note

KAUST Repository Item: Exported on 2021-04-05
Acknowledgements: Research reported in this publication was supported by the King Abdullah University of Science and Technology (KAUST).

ASJC Scopus subject areas

Artificial Intelligence
Applied Mathematics

Access to Document

10.1007/s10472-021-09734-6

https://repository.kaust.edu.sa/bitstream/10754/668490/1/Lozin-Moshkov2021_Article_CriticalPropertiesAndComplexit.pdf

Cite this

@article{fc9198c4158f45b1b9e56be1c16800c5,

title = "Critical Properties and Complexity Measures of Read-Once Boolean Functions",

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.",

author = "Vadim Lozin and Mikhail Moshkov",

note = "KAUST Repository Item: Exported on 2021-04-05 Acknowledgements: Research reported in this publication was supported by the King Abdullah University of Science and Technology (KAUST).",

year = "2021",

month = mar,

day = "22",

doi = "10.1007/s10472-021-09734-6",

language = "English (US)",

journal = "Annals of Mathematics and Artificial Intelligence",

issn = "1573-7470",

publisher = "Springer Netherlands",

}

TY - JOUR

T1 - Critical Properties and Complexity Measures of Read-Once Boolean Functions

AU - Lozin, Vadim

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2021-04-05 Acknowledgements: Research reported in this publication was supported by the King Abdullah University of Science and Technology (KAUST).

PY - 2021/3/22

Y1 - 2021/3/22

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/668490

UR - http://link.springer.com/10.1007/s10472-021-09734-6

UR - http://www.scopus.com/inward/record.url?scp=85103215318&partnerID=8YFLogxK

U2 - 10.1007/s10472-021-09734-6

DO - 10.1007/s10472-021-09734-6

M3 - Article

SN - 1573-7470

JO - Annals of Mathematics and Artificial Intelligence

JF - Annals of Mathematics and Artificial Intelligence

ER -

Critical Properties and Complexity Measures of Read-Once Boolean Functions

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this