10.23638/DMTCS-21-4-19
https://dmtcs.episciences.org/5565
Rosenkrantz, Daniel J.
Daniel J.
Rosenkrantz
Marathe, Madhav V.
Madhav V.
Marathe
Ravi, S. S.
S. S.
Ravi
Stearns, Richard E.
Richard E.
Stearns
Symmetry Properties of Nested Canalyzing Functions
Many researchers have studied symmetry properties of various Boolean
functions. A class of Boolean functions, called nested canalyzing functions
(NCFs), has been used to model certain biological phenomena. We identify some
interesting relationships between NCFs, symmetric Boolean functions and a
generalization of symmetric Boolean functions, which we call $r$-symmetric
functions (where $r$ is the symmetry level). Using a normalized representation
for NCFs, we develop a characterization of when two variables of an NCF are
symmetric. Using this characterization, we show that the symmetry level of an
NCF $f$ can be easily computed given a standard representation of $f$. We also
present an algorithm for testing whether a given $r$-symmetric function is an
NCF. Further, we show that for any NCF $f$ with $n$ variables, the notion of
strong asymmetry considered in the literature is equivalent to the property
that $f$ is $n$-symmetric. We use this result to derive a closed form
expression for the number of $n$-variable Boolean functions that are NCFs and
strongly asymmetric. We also identify all the Boolean functions that are NCFs
and symmetric.
Comment: 17 pages
episciences.org
Computer Science - Discrete Mathematics
Computer Science - Data Structures and Algorithms
68R99 (primary), 68W01 (secondary)
arXiv.org - Non-exclusive license to distribute
2019-11-26
2019-11-26
2019-11-26
eng
journal article
arXiv:1906.03752
10.48550/arXiv.1906.03752
1365-8050
10.48550/arxiv.1906.03752
https://dmtcs.episciences.org/5565/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
vol. 21 no. 4
Discrete Algorithms
Researchers
Students