Lozin, Vadim V. and Moshkov, Mikhail (2021) Critical properties and complexity measures of read-once Boolean functions. Annals of Mathematics and Artificial Intelligence, 89 . 595-614 . doi:10.1007/s10472-021-09734-6 ISSN 1012-2443.

Preview

PDF WRAP-critical-properties-complexity-measures-read-once-Boolean-functions-Lozin-2021.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (627Kb) | Preview

Request Changes to record.

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.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH):	Computational complexity, Algebra, Boolean
Journal or Publication Title:	Annals of Mathematics and Artificial Intelligence
Publisher:	Springer
ISSN:	1012-2443
Official Date:	June 2021
Dates:	Date Event June 2021 Published 22 March 2021 Available 24 February 2021 Accepted
Volume:	89
Page Range:	595-614
DOI:	10.1007/s10472-021-09734-6
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access (Creative Commons)
Date of first compliant deposit:	25 March 2021
Date of first compliant Open Access:	26 March 2021
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID UNSPECIFIED King Abdullah University of Science and Technology http://dx.doi.org/10.13039/501100004052

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads