Lozin, Vadim, Razgon, Igor, Zamaraev, Viktor 
ORCID: 0000-0001-5755-4141, Zamaraeva, Elena and Zolotykh, Nikolai
(2018)
Linear read-once and related Boolean functions.
DISCRETE APPLIED MATHEMATICS, 250.
pp. 16-27.
|
Text
1805.10159v1.pdf - Submitted version Download (239kB) | Preview |
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 func- tions 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. conjec- tured 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: | Article |
|---|---|
| Additional Information: | Submitted to Discrete and Applied Mathematics. arXiv admin note: text overlap with arXiv:1706.01747 |
| Uncontrolled Keywords: | Threshold function, Read-once function, Linear read-once function, Nested canalyzing function, Canalyzing function, Chow function |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 07 Sep 2020 08:05 |
| Last Modified: | 18 Jan 2023 23:35 |
| DOI: | 10.1016/j.dam.2018.05.001 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3100224 |
Dimensions
Dimensions
