eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2019-11-26
vol. 21 no. 4
Discrete Algorithms
10.23638/DMTCS-21-4-19
5565
journal article
Symmetry Properties of Nested Canalyzing Functions
Daniel J. Rosenkrantz
Madhav V. Marathe
S. S. Ravi
Richard E. Stearns
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.
https://dmtcs.episciences.org/5565/pdf
Computer Science - Discrete Mathematics
Computer Science - Data Structures and Algorithms
68R99 (primary), 68W01 (secondary)