Geodesic
Symmetry Properties of Nested Canalyzing Functions
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.23638/DMTCS-21-4-19
Classification : 05E05, 06E30 
@article{DMTCS_2019_21_4_a17,
     author = {Rosenkrantz, Daniel J. and Marathe, Madhav V. and Ravi, S. S. and Stearns, Richard E.},
     title = {Symmetry {Properties} of {Nested} {Canalyzing} {Functions}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2019},
     doi = {10.23638/DMTCS-21-4-19},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-19/}
}
TY  - JOUR
AU  - Rosenkrantz, Daniel J.
AU  - Marathe, Madhav V.
AU  - Ravi, S. S.
AU  - Stearns, Richard E.
TI  - Symmetry Properties of Nested Canalyzing Functions
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-19/
DO  - 10.23638/DMTCS-21-4-19
LA  - en
ID  - DMTCS_2019_21_4_a17
ER  - 
%0 Journal Article
%A Rosenkrantz, Daniel J.
%A Marathe, Madhav V.
%A Ravi, S. S.
%A Stearns, Richard E.
%T Symmetry Properties of Nested Canalyzing Functions
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-19/
%R 10.23638/DMTCS-21-4-19
%G en
%F DMTCS_2019_21_4_a17
Rosenkrantz, Daniel J.; Marathe, Madhav V.; Ravi, S. S.; Stearns, Richard E. Symmetry Properties of Nested Canalyzing Functions. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4. doi : 10.23638/DMTCS-21-4-19. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-19/

Cité par Sources :