The {\em asynchronous automaton} associated with a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$, considered in many applications, is the finite deterministic automaton where the set of states is $\{0,1\}^n$, the alphabet is $[n]$, and the action of letter $i$ on a state $x$ consists in either switching the $i$th component if $f_i(x)\neq x_i$ or doing nothing otherwise. These actions are extended to words in the natural way. A word is then {\em synchronizing} if the result of its action is the same for every state. In this paper, we ask for the existence of synchronizing words, and their minimal length, for a basic class of Boolean networks called and-or-nets: given an arc-signed digraph $G$ on $[n]$, we say that $f$ is an {\em and-or-net} on $G$ if, for every $i\in [n]$, there is $a$ such that, for all state $x$, $f_i(x)=a$ if and only if $x_j=a$ ($x_j\neq a$) for every positive (negative) arc from $j$ to $i$; so if $a=1$ ($a=0$) then $f_i$ is a conjunction (disjunction) of positive or negative literals. Our main result is that if $G$ is strongly connected and has no positive cycles, then either every and-or-net on $G$ has a synchronizing word of length at most $10(\sqrt{5}+1)^n$, much smaller than the bound $(2^n-1)^2$ given by the well known \v{C}ern\'y's conjecture, or $G$ is a cycle and no and-or-net on $G$ has a synchronizing word. This contrasts with the following complexity result: it is coNP-hard to decide if every and-or-net on $G$ has a synchronizing word, even if $G$ is strongly connected or has no positive cycles.


翻译:摘要:与布尔网络$f:\{0,1\}^n\to \{0,1\}^n$相关的异步自动机,在许多应用中都得到了广泛的应用。异步自动机是有限确定性自动机,在其中状态集是$\{0,1\}^n$,字母表为$[n]$,字母$i$对状态$x$的动作可以将第$i$个分量切换,如果$f_i(x)\neq x_i$,否则不做任何动作。这些操作自然地扩展到单词中。当且仅当一个单词的动作对于每个状态得到相同的结果时,这个单词就是“同步的”。在本文中,我们探究一个基本类的布尔网络,名为“与或网”的同步单词的存在性及其最小长度:对于给定的弧符号图$G$和$n$,如果$f$ 满足对于每个$i∈[n]$,都存在$a$,使得对于所有状态$x$,如果$j$ 到$i$有正边(负边),则当且仅当$x_j=a$ ($x_j\neq a$)时,$f_i(x)=a$。因此,如果$a=1$($a=0$),则$f_i$是正(负)文字的合取(析取)。本文的主要结果表明,如果$G$是强连通且没有正循环,则任何$G$上的与或网都存在一个长度不超过$10(\sqrt{5}+1)^n$的同步单词,这比众所周知的Černý猜想 给出的上界$(2^n-1)^2$要小得多,或者$G$是一个环且没有任何$G$上的与或网存在同步单词。这与以下复杂性结果形成对比:即使在$G$强连通或没有正循环的情况下,判断是否每个与或网都存在同步单词也是coNP-难的。

0
下载
关闭预览

相关内容

【硬核书】树与网络上的概率,716页pdf
专知会员服务
72+阅读 · 2021年12月8日
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
50+阅读 · 2020年12月14日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
31+阅读 · 2020年4月15日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
已删除
将门创投
14+阅读 · 2019年5月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
美国化学会 (ACS) 北京代表处招聘
知社学术圈
11+阅读 · 2018年9月4日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
揭开知识库问答KB-QA的面纱3·信息抽取篇
PaperWeekly
15+阅读 · 2017年8月14日
时延神经网络(TDNN)原理及其TensorFlow实现
深度学习每日摘要
56+阅读 · 2017年5月19日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月29日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
已删除
将门创投
14+阅读 · 2019年5月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
美国化学会 (ACS) 北京代表处招聘
知社学术圈
11+阅读 · 2018年9月4日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
揭开知识库问答KB-QA的面纱3·信息抽取篇
PaperWeekly
15+阅读 · 2017年8月14日
时延神经网络(TDNN)原理及其TensorFlow实现
深度学习每日摘要
56+阅读 · 2017年5月19日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员