تقرير
Symmetry Properties of Nested Canalyzing Functions
| العنوان: | Symmetry Properties of Nested Canalyzing Functions |
|---|---|
| المؤلفون: | Rosenkrantz, Daniel J., Marathe, Madhav V., Ravi, S. S., Stearns, Richard E. |
| المصدر: | Discrete Mathematics & Theoretical Computer Science, vol. 21 no. 4, Discrete Algorithms (November 26, 2019) dmtcs:5565 |
| سنة النشر: | 2019 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms |
| الوصف: | 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 |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.23638/DMTCS-21-4-19 |
| URL الوصول: | http://arxiv.org/abs/1906.03752 |
| رقم الأكسشن: | edsarx.1906.03752 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.23638/DMTCS-21-4-19 |
|---|