episciences.org_5565_1675655429 1675655429 episciences.org raphael.tournoy+crossrefapi@ccsd.cnrs.fr episciences.org Discrete Mathematics & Theoretical Computer Science 1365-8050 11 26 2019 vol. 21 no. 4 Discrete Algorithms 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. 11 26 2019 5565 https://arxiv.org/licenses/nonexclusive-distrib/1.0 arXiv:1906.03752 10.48550/arXiv.1906.03752 https://arxiv.org/abs/1906.03752v2 https://arxiv.org/abs/1906.03752v1 10.23638/DMTCS-21-4-19 https://dmtcs.episciences.org/5565 https://dmtcs.episciences.org/5920/pdf https://dmtcs.episciences.org/5920/pdf