Linear read-once and related Boolean functions

DOI10.1016/J.DAM.2018.05.001MaRDI QIDQ1801039zbMATH OpenOpenAlexWikidataFDO

Authors Vadim Lozin, Igor Razgon, Elena Zamaraeva, Victor Zamaraev, N. Yu. Zolotykh

Publication date 26 October 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.10159, https://eprints.bbk.ac.uk/id/eprint/23545/1/1805.10159.pdf

zbMATH Keywords

canalyzing functionChow functionlinear read-once functionnested canalyzing functionread-once functionthreshold function

Mathematics Subject Classification ID

Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10)

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.

Recommendations

• Specifying a positive threshold function via extremal points
• Functions that are read-once on a subset of their inputs
• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• scientific article; zbMATH DE number 5852793
• scientific article; zbMATH DE number 176867

Cites work

• Boolean nested canalizing functions: a comprehensive analysis
• Decision lists and related Boolean functions
• Enumeration of Seven-Argument Threshold Functions
• Estimating the complexity of deciphering a threshold functions in a k-valued logic
• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 3266648 (Why is no real title available?)
• Nested canalyzing, unate cascade, and polynomial functions
• On almost bad Boolean bases
• On specifying Boolean functions by labelled examples
• Specifying a positive threshold function via extremal points

Cited in

(4)

• On specifying Boolean functions by labelled examples
• Critical properties and complexity measures of read-once Boolean functions
• On Boolean threshold functions with minimum specification number
• A characterization of 2-threshold functions via pairs of prime segments

Describes a project that uses

Uses Software

• JBool

This page was built for publication: Linear read-once and related Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801039)