论文标题
关于自动机网络中的模拟
On simulation in automata networks
论文作者
论文摘要
自动机网络是一个有限的图形，每个节点都从某些有限字母内保存状态，并配备了一个更新功能，该功能根据相邻状态的配置改变其状态。更简单地，它由有限的地图$ f：q^n \ rightarrow q^n $给出。在本文中，我们研究了如何通过使用规定的更新模式或交互图的其他（集合）自动机网络（集合）网络（集合）网络。我们的贡献如下。对于非树立字母和任何网络大小，都有本质上的非序列转换（即无法作为某些网络的顺序更新的组成获得）。此外，没有通用自动机网络可以通过异步更新的组成产生所有非限值功能。另一方面，如果允许使用较大的字母，然后将投影或限制到原始字母内，则表明有通用自动机网络用于顺序更新。我们还表征了由非限值顺序更新生成的一组函数。在Tchuente之后，我们表征了交互图$ d $，其转换的半群是$ q^n $上的完整转换的完整半群，并且我们表明，如果我们强制执行顺序更新或所有异步更新，则它们是相同的。
An automata network is a finite graph where each node holds a state from some finite alphabet and is equipped with an update function that changes its state according to the configuration of neighboring states. More concisely, it is given by a finite map $f:Q^n\rightarrow Q^n$. In this paper we study how some (sets of) automata networks can be simulated by some other (set of) automata networks with prescribed update mode or interaction graph. Our contributions are the following. For non-Boolean alphabets and for any network size, there are intrinsically non-sequential transformations (i.e. that can not be obtained as composition of sequential updates of some network). Moreover there is no universal automaton network that can produce all non-bijective functions via compositions of asynchronous updates. On the other hand, we show that there are universal automata networks for sequential updates if one is allowed to use a larger alphabet and then use either projection onto or restriction to the original alphabet. We also characterize the set of functions that are generated by non-bijective sequential updates. Following Tchuente, we characterize the interaction graphs $D$ whose semigroup of transformations is the full semigroup of transformations on $Q^n$, and we show that they are the same if we force either sequential updates only, or all asynchronous updates.
