Characterization of Linearly Separable Boolean Functions: A Graph-Theoretic Perspective.
basic_science · Level V
Where this comes from
- Record sourced from PubMed, PMID 27076471.
- Also identified by DOI 10.1109/TNNLS.2016.2542205.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
Abstract
In this paper, we present a novel approach for studying Boolean function in a graph-theoretic perspective. In particular, we first transform a Boolean function f of n variables into an induced subgraph H<sub>f</sub> of the n -dimensional hypercube, and then, we show the properties of linearly separable Boolean functions on the basis of the analysis of the structure of H<sub>f</sub> . We define a new class of graphs, called hyperstar, and prove that the induced subgraph H<sub>f</sub> of any linearly separable Boolean function f is a hyperstar. The proposal of hyperstar helps us uncover a number of fundamental properties of linearly separable Boolean functions in this paper.