Linear read-once and related Boolean functions

Lozin, Vadim; Razgon, Igor; Zamaraev, Viktor; Zamaraeva, Elena; Zolotykh, Nikolai

Abstract

It is known that a positive Boolean function depending on variables has at least extremal points, i.e. minimal ones and maximal zeros. We show that has exactly 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 for functions depending on variables. In 1995 Anthony et al. conjectured that for all other threshold functions the specification number is strictly greater than . We disprove this conjecture by exhibiting a threshold non-linear read-once function depending on variables whose specification number is .

Citation

Lozin, V., Razgon, I., Zamaraev, V., Zamaraeva, E., & Zolotykh, N. (2018). Linear read-once and related Boolean functions. Discrete Applied Mathematics, 250, 16-27. https://doi.org/10.1016/j.dam.2018.05.001

• Journal Article Type: Article
• Acceptance Date: May 4, 2018
• Online Publication Date: Jun 14, 2018
• Publication Date: Jun 14, 2018
• Deposit Date: Nov 9, 2018
• Publicly Available Date: Jan 3, 2024
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 250
• Pages: 16-27
• DOI: https://doi.org/10.1016/j.dam.2018.05.001
• Public URL: https://durham-repository.worktribe.com/output/1313835