{"docId":5920,"paperId":5565,"url":"https:\/\/dmtcs.episciences.org\/5565","doi":"10.23638\/DMTCS-21-4-19","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":373,"name":"vol. 21 no. 4"}],"section":[{"sid":7,"title":"Discrete Algorithms","description":[]}],"repositoryName":"arXiv","repositoryIdentifier":"1906.03752","repositoryVersion":3,"repositoryLink":"https:\/\/arxiv.org\/abs\/1906.03752v3","dateSubmitted":"2019-06-11 16:12:16","dateAccepted":"2019-11-26 08:11:51","datePublished":"2019-11-26 14:39:22","titles":["Symmetry Properties of Nested Canalyzing Functions"],"authors":["Rosenkrantz, Daniel J.","Marathe, Madhav V.","Ravi, S. S.","Stearns, Richard E."],"abstracts":["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"],"keywords":["Computer Science - Discrete Mathematics","Computer Science - Data Structures and Algorithms","68R99 (primary), 68W01 (secondary)"]}