Daniel J. Rosenkrantz ; Madhav V. Marathe ; S. S. Ravi ; Richard E. Stearns - Symmetry Properties of Nested Canalyzing Functions

dmtcs:5565 - Discrete Mathematics & Theoretical Computer Science, November 26, 2019, vol. 21 no. 4 - https://doi.org/10.23638/DMTCS-21-4-19
Symmetry Properties of Nested Canalyzing FunctionsArticle

Authors: 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.


    Volume: vol. 21 no. 4
    Section: Discrete Algorithms
    Published on: November 26, 2019
    Accepted on: October 29, 2019
    Submitted on: June 11, 2019
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Data Structures and Algorithms,68R99 (primary), 68W01 (secondary)
    Funding:
      Source : OpenAIRE Graph
    • III: Small: Collaborative Research: Explaining Unsupervised Learning: Combinatorial Optimization Formulations, Methods and Applications; Funder: National Science Foundation; Code: 1908530
    • EAGER: SSDIM: Ensembles of Interdependent Critical Infrastructure Networks; Funder: National Science Foundation; Code: 1745207
    • Collaborative Research: Framework: Software: CINES: A Scalable Cyberinfrastructure for Sustained Innovation in Network Engineering and Science; Funder: National Science Foundation; Code: 1916805
    • CIF21 DIBBs: Middleware and High Performance Analytics Libraries for Scalable Data Science; Funder: National Science Foundation; Code: 1443054

    Consultation statistics

    This page has been seen 1460 times.
    This article's PDF has been downloaded 238 times.