Boolean nested canalizing functions (NCFs) have important applications in molecular regulatory networks, engineering and computer science. In this paper, we study their certificate complexity. For both Boolean values $b\in\{0,1\}$, we obtain a formula for $b$-certificate complexity and consequently, we develop a direct proof of the certificate complexity formula of an NCF. Symmetry is another interesting property of Boolean functions and we significantly simplify the proofs of some recent theorems about partial symmetry of NCFs. We also describe the algebraic normal form of $s$-symmetric NCFs. We obtain the general formula of the cardinality of the set of $n$-variable $s$-symmetric Boolean NCFs for $s=1,\dots,n$. In particular, we enumerate the strongly asymmetric Boolean NCFs.


翻译:布尔巢型运河功能(NCFs)在分子监管网络、工程和计算机科学中具有重要的应用性。在本文中,我们研究了它们的证书复杂性。对于布尔值 $b\ in ⁇ 0,1 ⁇ $,我们获得了一个美元证书复杂性的公式,因此,我们开发了一个关于NCF证书复杂性公式的直接证明。对称是布尔函数的另一个有趣的属性,我们大大简化了最近一些理论的证明,以证明NCFs部分对称。我们还描述了美元对称NCFs的正数正数形式。我们获得了一套美元可变值美元对称布伦型NCFs的基本公式,用于$=1,\dots,n美元。我们特别列举了强称不对称布尔值的NCFs。

0
下载
关闭预览

相关内容

专知会员服务
166+阅读 · 2021年8月3日
【Cell】神经算法推理,Neural algorithmic reasoning
专知会员服务
28+阅读 · 2021年7月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
Nature 一周论文导读 | 2019 年 2 月 28 日
科研圈
13+阅读 · 2019年3月10日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
将门创投
5+阅读 · 2018年11月27日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Arxiv
0+阅读 · 2022年1月28日
Arxiv
0+阅读 · 2022年1月27日
Arxiv
4+阅读 · 2018年1月15日
VIP会员
相关VIP内容
专知会员服务
166+阅读 · 2021年8月3日
【Cell】神经算法推理,Neural algorithmic reasoning
专知会员服务
28+阅读 · 2021年7月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
Nature 一周论文导读 | 2019 年 2 月 28 日
科研圈
13+阅读 · 2019年3月10日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
将门创投
5+阅读 · 2018年11月27日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Top
微信扫码咨询专知VIP会员