论文标题
异步同步布尔网络
Synchronizing Boolean networks asynchronously
论文作者
论文摘要
与布尔网络$ f：\ {0,1 \}^n \至\ {0,1 \}^n $相关的{\ em异步自动机}，在许多应用中考虑，在许多应用中考虑，是有限的确定性自动机，是$ \ \ \ i \ ies $ i的$ i $ i $ i，$ i，$ i，$ i，$ i，$ i，$ i，$ i，$ i，$ i，$ i，$ i $ i是$ i。如果$ f_i（x）\ neq x_i $切换$ i $ th组成部分，则状态$ x $是组成的。这些动作以自然的方式扩展到文字。如果每个状态的动作结果相同，则单词是{\ em同步}。在本文中，我们要求存在同步的单词及其最小的长度，用于基本的布尔网络，称为and-or-nets：给定$ [n] $上的Arc签名的Digraph $ g $，我们说$ f $是$ g $ in $ g $，对于所有$ i $ i $ $ f_i（x）= a $，仅当$ x_j = a $（$ x_j \ neq a $）的每个正（负）弧线从$ j $到$ i $;因此，如果$ a = 1 $（$ a = 0 $），则$ f_i $是正面或负面文字的连词（脱节）。 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 Černý's conjecture, or $G$ is a cycle and no and-or-net on $G$ has a同步单词。这与以下复杂性结果形成鲜明对比：决定$ g $上的每个及网络是否具有同步的单词，即使$ g $连接或没有正面周期，也是如此。
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 Černý'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.
