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 -