The Library
Linear read-once and related Boolean functions
Tools
Lozin, Vadim V., Razgon, Igor, Zamaraev, Victor, Zamaraeva, Elena and Zolotykh, Nikolai (2018) Linear read-once and related Boolean functions. Discrete Applied Mathematics, 250 . pp. 16-27. doi:10.1016/j.dam.2018.05.001 ISSN 0166-218X.
|
PDF
WRAP-linear-read-once-related-Boolean-functions-Lozin-2018.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (657Kb) | Preview |
Official URL: https://doi.org/10.1016/j.dam.2018.05.001
Abstract
It is known that a positive Boolean function f depending on n variables has at least n + 1 extremal points, i.e. minimal ones and maximal zeros. We show that f has exactly n + 1 extremal points if and only if it is linear read-once.
The class of linear read-once functions is known to be the intersection of the classes of read-once and threshold functions. Generalizing this result we show that the class of linear read-once functions is the intersection of read-once and Chow functions. We also find the set of minimal read-once functions which are not linear read-once and the set of minimal threshold functions which are not linear read-once. In other words, we characterize the class of linear read-once functions by means of minimal forbidden subfunctions within the universe of read-once and the universe of threshold functions.
Within the universe of threshold functions the importance of linear read-once functions is due to the fact that they attain the minimum value of the specification number, which is n + 1 for functions depending on n variables. In 1995 Anthony et al. conjectured that for all other threshold functions the specification number is strictly greater than n+ 1. We disprove this conjecture by exhibiting a threshold non-linear read-once function depending on n variables whose specification number is n + 1.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Library of Congress Subject Headings (LCSH): | Algebra, Boolean, Functions, Algebraic functions | ||||||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||||||
Publisher: | Elsevier Science Ltd. | ||||||||
ISSN: | 0166-218X | ||||||||
Official Date: | 11 December 2018 | ||||||||
Dates: |
|
||||||||
Volume: | 250 | ||||||||
Page Range: | pp. 16-27 | ||||||||
DOI: | 10.1016/j.dam.2018.05.001 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 21 May 2018 | ||||||||
Date of first compliant Open Access: | 14 June 2019 | ||||||||
RIOXX Funder/Project Grant: |
|
||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year