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.
@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
Cité par Sources :