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-难的。