⊕⊕⊕⊕⊕⊕⊕可在www.sciencedirect.com在线获取理论计算机科学电子笔记326（2016）3-25www.elsevier.com/locate/entcs异步局部非单调布尔自动机网络的植物群AuroreAlcolei1K'evinPerrot2SylvainSenn'e3Aix-MarseilleUniversit'e，CNRS，LIFUMR 7279，13288Marseille，France摘要布尔自动机网络（BAN）是一种成熟的调控系统模型，如神经网络或基因调控网络。BAN的异步动力学的研究主要集中在单调的网络，其中的静态和动态特性的链接的基本问题已经提出和解决。本文探讨了类似的问题，非单调网络，-BAN（异或BAN），这是BAN的所有本地转移功能是-功能。利用算法工具，我们给出了大多数强连通图的异步转移图的一般特征。- BAN和仙人掌- BAN作为这些结果的一个例子，我们提供了一个完整的描述的异步动态的两个特定结构的BAN，即花和循环链。这项工作还绘制了BAN之间的新的行为等价物，使用重写规则对它们的图形描述。关键词：交互网络，布尔自动机网络，非单调性，异步动态，行为等价。1引言布尔自动机网络（BAN）是离散的相互作用网络，其现在是用于生物调节系统（例如神经网络[9，10]或基因调节网络[12，23]）的良好建立的模型。在这种程度上，局部单调BAN已经在应用方面[8，15]和理论方面[11，14，17，19，20]得到了广泛的研究。然而，最近的工作带来了新的兴趣，在当地的非单调性[18]。在生物学方面，已经表明，有时，基因调控意味着比通常假设的更复杂的行为：例如，当人们还考虑到其副产物的影响时，情况就是如此[22]。在这种情况下，1电子邮件：aurore. ens-lyon.fr2电子邮件：kevin. lif.univ-mrs.fr3电子邮件：sylvain. lif.univ-mrs.frhttp://dx.doi.org/10.1016/j.entcs.2016.09.0161571-0661/© 2016作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。4A. Alcolei等人/理论计算机科学电子笔记326（2016）3i=1建模可能需要非单调性，特别是因为这允许表达对环境的敏感性在理论方面，已经注意到[16，19]，当涉及BAN中的奇异行为时，通常涉及非局部单调性。例如，已经证明，对同步添加不鲁棒的最小网络（即允许一些自动机同时更新）是局部非单调BAN [16，19]。按照[18]的思路，本研究是更好地理解局部非单调BAN的第一步。它主要关注的是BAN，即通过对状态值（或否定状态）进行异或来更新自动机i的状态的BAN值）的传入邻居i.换句话说，在这些BAN中，每个局部转移函数的形式为j∈N+（i）σ（xj），其中σ∈{id，neg}，N+（i）表示i的传入邻居的集合[19]。遵循一种建设性的方法，我们首先研究了一些组合循环的特定BAN结构，例如双循环图[3，13]，双幂图[4]和循环链。所有这些BAN都属于仙人掌BAN家族，因为它们结构中的任何两个简单循环最多有一个共同的自动机。实际上，我们意识到，我们从这些BAN中得到的大多数具体结果实际上都可以推广到一组广泛的BAN：强连接的BAN，其诱导双环的大小大于3。第2节中给出了这些BAN的精确说明。本节还介绍了将在续集中使用的所有定义和符号第三节是专门介绍和证明的一般结果所获得的异步动力学的强连接的双循环的大小大于3。与[13]中所做的类似，这些结果基于这些BAN的异步转换图的算法描述。我们在第4节中总结了两种类型的BAN的完整特征，即BANs-低BAN和BAN-循环链BAN，这说明了第3节的结果，并提供了BANs特有的新的行为等价互模拟结果。这些最后的结果是有趣的，因为他们提供了新的视角BAN分类通过使用重写的相互作用图。2定义和符号BAN的静态定义BAN被定义为一组相互作用的布尔自动机。网络的大小对应于其中自动机的数量。对于大小为n的网络N，我们表示V ={1，...， n}对应的自动机集合。布尔自动机i是一个状态具有布尔值xi∈B={0，1}。 布尔向量x =（xi）n，它将所有网络中的自动机被称为N的配置。在下文中，我们将有时用x [i，k]表示记录自动机从i到k的状态的子向量，对于i< k。我们将配置x缩短xi，其中第i个自动机的状态被否定，类似地，对于V的任何子集I，xi将表示A. Alcolei等人/理论计算机科学电子笔记326（2016）35i=1.Σi=1j=1配置x，其中I中自动机的状态被否定。自动机的状态可以根据其局部转移函数fi：Bn→B进行更新。这个局部函数描述了自动机在给定配置下的反应：刚被更新后，i的状态具有值fi（x），其中x是更新前网络的配置。我们说i在x中是稳定的，如果fi（x）= xi。否则它是不稳定的。因此，网络N被完全描述为由其局部转移函数N ={fi}n.一个自动机i被称为是一个自动机j的一个输入，如果存在一个配置x使得fj（x）/=fj（xi）。在这种情况下，j被认为是由i. 我们用Ij表示j的整数的集合。在BAN中，路径π = i0i1... 长度为k的ik是一个不同的自动机序列，使得对于所有1 ≤j≤k，ij−1∈Ij。 一个BAN是强连通的，如果有每两个自动机之间的路径。裸路径是一条特定的路径， 对于所有的1 ≤j≤k，ij−1是i j的唯一单位元（Ij={ij−1}），即fj（x）= xj−1或fj（x）= xj−1。我们将裸路的符号定义为组成裸路的形式为fi（x）= xi−1的局部函数的个数的奇偶性，即 符号（π）=nj=1 1fj（x）=xj−1Σmod（2）。 一条裸路径是最大的，如果它的任何扩展不是一条裸路我们用πi表示在自动机中结束的最大裸路i. 路径和裸路径的名称来自于通常与BAN相关联的图形表示，我们将在下面看到为了了解网络的样子，通常会给出它的图形表示。 对于每一个局部函数fi，我们可以在变量xi上关联一个布尔公式Fi。与变量xi的第k次出现相关联的文字由σk（xi）表示，其中σk是文字的符号。则根据这些公式的N的交互图是符号有向图G=（V，A），其中V ={1，.， n}是G中每个文字在F i中有一个入口点的节点的集合，A是由（i，j，σk）∈ A定义的弧的集合，如果变量xi在Fj中的第k次出现具有符号σk（见图1（a））。当我们关注于BAN时，所有涉及多个自动机的公式Fi都将被写成Reed-Muller标准形式，即Fi= j∈Iiσj（xj）。BAN的类型将涉及其交互图的底层结构（以符号为模的字面量和自动机的重命名）。一种类型的BAN可以用一个图族来描述，如果两个BAN的交互图是同构的（我们忽略标签），我们就说它们是同一类型的允许复杂行为的最简单的交互结构是循环结构[21]。 一个大小为n的布尔自动机循环（BAC）C是一个BAN，作为一组局部函数{fi}n，使得fi（x）= x（（i−1））mod（n）） 或fi（x）=x（（i−1）mod（n）） 对于所有i∈{1，...，n}。 我们经常滥用符号表示f，通过它的公式表示Fi=σi（xpred（i）），其中pred（i）=（i−1 mod（n））是C中i的唯一整数，σi是它的符号（单位或否定函数）。在下文中，我们讨论的大多数网络或模式都是由相互交叉的循环组成的。 如果一个自动机i是l个不同的循环，则其局部转移函数将为fi（x）=lσj（predj（i）），其中6A. Alcolei等人/理论计算机科学电子笔记326（2016）3C∈i=1t=11N1Predj（i）表示每个入射周期中i的前驱如果用m个简单循环的交点来描述BAN，C1，.，Cm，我们通常将其大小表示为自然数n =（n1，...，nm），其中nk是第k个循环的大小。 我们还将使用该向量表示来描述BAN的配置：x =（x1，...，xm）∈Bn1×. ×Bnm将表示每个循环k处于配置xkBnk的配置。通过扩展，xk将表示自动机i k的状态，i k 是J J循环Ck.正如人们所预期的，强连接的BAN是一个BAN，其相互作用图是强连通的。因此，这些BAN的类型总是可以描述为一组简单的循环和交叉自动机。强连通仙人掌BAN是一种特殊的强连通BAN，其中任何两个简单的循环彼此相交至多一次[5]。这种形式的BAN的最简单示例是布尔自动机双循环（BADC）。这些BAN由两个循环C1，C2描述，它们相交于唯一的自动机o = i1= i2。禁止吸烟图1（a）中所示的实际上是大小为（2，1）= 2 + 1− 1 = 2的BADC。BAN的异步动态如前所述，网络的配置可能会随着正在发生的本地更新而发生变化。局部更新由V的子集W正式描述，其中包含每次更新的自动机。我们说W是异步的，如果它的基数为1，也就是说，对于某些i∈V。更新W使系统从配置x移动到配置xJ，其中如果i ∈ W，则xJi = fi（x），否则xJi= xi。 这在配置集上定义了一个全局函数FW：Bn→Bn。如果网络的所有移动都是由于来自M的更新，则网络根据特定的模式MP（V）演化。大小为n的BAN的异步模式则为由异步更新的集合A={{i}}n定义，它是不确定的。请注意，我们对更新模式的定义并不完全通用[17]，但对于本文的范围我们说一个配置xJ是从一个配置x可达的（在一个模式M) ）如果存在更新的有限序列（Wt）s（在M中），使得FW 我... ◦1FWs（x）=xJ.然后，如果无法到达，则配置不可达（在M中）除了它自己之外，任何其他的配置（在M中）。最后，（M的）一个不动点是一个配置x，使得对于每个更新W（M中），FW（x）=x研究特定更新模式下的网络动力学旨在进行预测，即给定初始配置x，我们想知道网络可以渐近结束的可能配置集这些集合被称为网络的吸引子，而可以到达它们的配置集是它们的吸引盆。注意，一个固定点是一个大小为1的吸引子。根据更新模式M的网络N的动态可以被建模通过标号有向图GM=（Bn，W∈M FW），称为M-转移图A. Alcolei等人/理论计算机科学电子笔记326（2016）37id（）⊕关于我们N一加 二−+{1}{2}{1}、{ 2}(a)（b）第（1）款Fig. 1. （a）BAN的交互图f1（x）=x2，f2（x）=x1x2，（b）它的异步转移图.的N，使得：• Bn的顶点集对应于N的2n个构形。• 弧定义为函数FW对所有W ∈ M的转移图，即x−W→xJ是G的弧当且仅当W∈M且FW（x）=xJ。转移图GAN 与异步更新模式相关联的称为G的异步转移图，简称ATG。图1（b）显示了在左边描绘的BADC用转移图的方法，模M的吸引子对应于GM的一个终端强连通分支，即一个强连通分支。N不允许任何传出弧的组件。吸引盆地的一个吸引子对应于GM中连接到该吸引子的配置集成分N在模式M中，不属于吸引子的组态被称为瞬态组态。这些配置可以是可逆的或不可逆的，取决于一旦它们被通过，是否有可能再次达到它们。一种特殊类型的不可逆构形是不可达构形，这种构形没有任何传入弧，但在 GM.N由于转移图和动力学之间的对应关系，下面给出的结果用我们研究的网络的异步转移图的遍历和描述来表示行为同构互模拟等价关系我们以一个关于行为同构的快速提示来结束本节这是BAN集合上的等价关系，它表达了以下事实：两个网络“以相同的方式行为”（直到它们的自动机和/或它们的配置的重命名）。更确切地说，N和NJ的等价性意味着，对于任意的更新模式M，转移图GM和GM是同构的。N N′定义2.1两个BANN和NJ是（行为上）同构的，如果存在两个双射<$：在自动机集合上的V→VJ和在配置集合上的φ：Bn→Bn，使得对于N中的任何更新W<$V，相应的更新<$（W）在NJ中以相同的方式起作用，即对于所有配置x，φ（FW（x））=00{2}{2}01{1}{1}10118A. Alcolei等人/理论计算机科学电子笔记326（2016）3⇔Vi=1i=1我 i=1i=1我 i=11111111111i=1我i=1FJ（W）（φ（x））.BAN之间同构的定义首先在[17]中以互模拟的名义我们在这里回顾一些关于它的一般结果定理2.2（[17]）设N={fi}n是BAN，N∈{fi}n成为它的对偶网络定义为fi（x）= fi（x），则N和N同构。定理2.3（[17]）设N={fi}n是一个BAN，N+={f+}n是它的正则-一种典型网络，定义为：（i）f+（x）=xj，如果fi（x）=xj或xj，以及（ii）f+（x）=fi（xI）我我否则，其中I ={i ∈ V |sign（πi）= 1}是一组自动机，传入的裸体路径有负号。 那么N和N+是同构的。定理2.2是重要的，因为它告诉我们，所有的结果在续集中也将成立的惠BAN，这是对偶BANs的BAN因为它们所有的局部函数都是fi（x）=j∈Ii σ（xj）。 在另一边，定理2.3在研究特定类型的网络时非常有用，因为它大大减少了研究的案例数量。事实上，它说，人们只需要关注具有正裸路径的网络，就可以对给定类型的网络的整个可能的转移图集进行例如，它指出，只有三种不同的情况下的BADCs的研究：积极的，消极的和混合的，分别对应的情况下，fo（x）=x1<$x2，fo（x）=x1<$x2和fo（x）=x1<$x2。实际上只有一类BADC因为：（i）等式x1<$x2=x1<$x2意味着正和负的BADC是平凡同构的;（ii）正的BADC同构于混合的BADC同样的结构，取φ（x）=x。为了证明两个网络是同构的，我们通常会使用比定义2.1中给出的条件更强的条件。引理2.4两个BANN={fi}n ，NJ={FJ}n同构当且仅当如果存在双射，则{1，...，n} → {1，...，n}和集合{φi：B→B}n（非常数）布尔函数使得对于所有自动机i，φi∈ {id，neg}，对于所有llc上的图形x∈Bn，φi（fi（x））=fJ（i）（φ（x）），其中eφ（x）按分量定义为φ（x）i= φ−1（i）（x−1（i））。证据右蕴涵的证明是直接的，因为局部函数之间的等式φi（fi（x））=fJ（i）（φ（x））导出了全局函数之间的等式yφ（FW（x））=Fj（W）（φ（x））。为了证明逆蕴涵，我们需要证明每个双射φ可以局部表示：假设N和NJ是同构的，并且令φ和φ符合定义2.1。对于所有的i∈{1，.，n}，设φi：Bn→B定义为φi（x）=φ（x）<$（i）。我们想证明φi不依赖于除xi以外的任何其他变量（因此它可以重写为从B →B的布尔函数）。A. Alcolei等人/理论计算机科学电子笔记326（2016）39我（j）⎩设j ∈ {1，.，设x为任意一种构型，则根据定义，φ（F（x））=φ（x）ifj在x中稳定和FJ（j）<$φ（xj）如果j在x（φ（x））=φφ（x）ifφ（j）isableiinφ（x）φ（x）函数φ是一个双射，所以φ（x）如果φ（j）在φ（x）φ（xj）。同时，φ（Fi（x））=FJ（j）（φ（x）），因此φ（xj）/= φ（x）意味着φ（xj）= φ（x）<$（j）（f = φ（x））。所以如果j=i，那么对于所有的x，φi（xj）=φ（xj）（i）（j）=（φ（x））（i）=φ（x）（j）=φi（x）所以φi不依赖于xj，对于所有j ∈ {1，.，n}−{i}，所以φi只依赖于xi。最后，φi是双射的，因为φ是双射。证明到此结束。□在第4节中，我们将充分利用定理2.3和引理2.4，给出新的同构结果。3关于BAN的一般结果这一部分给出了本文的主要定理：一个连通性结果，它刻画了任何强连通的BADC大于3的BAN的ATG的形状。定理3.1在强连接的BADC-BAN中，诱导的BADC的大小大于3，任何不是不可达的配置都可以从任何在二次异步更新中不稳定的配置到达。这个定理告诉我们，任何强连通的非圈或团的BAN的ATG的特征在于（见图2）：• 他的《易经》，《易经》。• 其不可达的配置U（如有）。• 可逆瞬态配置的唯一强连接分量（SCC），可从U\S的任何配置到达并连接到S\U的任何配置。定理3.1的证明是基于几种算法，这些算法描述了从一个给定的配置移动到一个ATG-BAN的另一个配置的更新序列。我们从介绍这些算法开始这一节。第二次我们简要地讨论了这些算法的复杂性，给出了算法长度的上界两个配置之间的最小更新序列。本节的结尾是关于任何BAN的不动点集和不可达配置的一般性评论，有助于精确定理3.1的结果。10A. Alcolei等人/理论计算机科学电子笔记326（2016）3J⊕u1S1.SCC.ukSL图二、诱导的BADC大于3的强连通BAN的一般ATG形状定理3.1的证明设N是一个强连通的BABAN，其诱导的BADCB的大小大于3，设x是它的初始（不稳定）配置，设x是配置够得着 定理3.1的证明背后的想法是利用B-BADC的高表达性，并使用B作为更确切地说，如果B处于不稳定的配置，那么我们将证明，给定一个自动机i和一个布尔值b，N总是可以移动到一个配置，其中i处于状态b，B是不稳定的。一个很好的直觉是，在一个正的BADC中，如果中央自动机从它的一个输入端接收到一个布尔值1，那么它可以通过沿着相反的周期发送自己的状态来切换状态。为了明确这一点，假设xpred1（o）= 1，然后沿着C2更新自动机将导致xpred2（o）=xo的配置，因此fo（x）=xpred1（o）<$x pred2（o）=1xo =xo。因此，在正网络中，可以将任何自动机i设置为通过将O设置为B，然后沿着从O到I的路径传播B，此外，可以确保这将再次成为可能，如果最终o的两个前驱中至少有一个处于状态1。为了形式化这个推理，定理3.1的证明基于以下两个引理。引理3.2在一个-BADC中，每个不是不可达的配置都可以在O（n 2）更新中从任何其他（不稳定）配置到达（并且边界是紧的）。证据首先，让我们回顾一下，所有相同大小（n1，n2）的BADC在行为同构方面是等价的。这特别意味着它们的ATG是同构的，因此证明引理3.2对正的BADC成立对于完整地证明引理3.2是足够的。因此，在下文中，我们将假设B是正的。然而，人们会注意到，下面的证明很容易调整到任何-BADC。我们证明引理3.2，提出一个算法，解释如何从一个（不稳定）配置到另一个（可达）在ATG的任何积极的BADC- 至少有一个循环的大小大于3。该算法可调谐以处理其中n1和n2都小于或等于2的BADC，但这A. Alcolei等人/理论计算机科学电子笔记326（2016）311n1Jn2n1我n1n2n1n21n1n2{1}|{2}0010{1}{2}{1}{2}01{1}11{2}{1}|{2}|{3}{2{1}{3}{3}{1}{2}{1}{3}{1}{3}101{2}111{2}{1}|{3}{3}{2}|{3}图3.第三章。大小为（1， 2）（左）和（2， 2）（右）的阳性BADC的ATG增加了需要考虑的案例数量，掩盖了总体动态。所以对于大小为（n1，n2）=（1，2）（或反之亦然）和（n1，n2）=（2，2）的BADC的特殊情况，我们更倾向于通过直接查看它们的ATG的形式来证明引理3.2。这些ATG如图3所示，它们都满足引理3.2。我们现在假设n=13。该算法分为两个步骤（如图4所示）：(i) 任何不稳定的配置（即，在状态1中至少有一个自动机的情况下，积极的BADC），可以达到高表达的交替配置x， 其中xo= fo（x）和xi= fi（x），对于所有i/= o（即， xo=Xn，并且对于所有ik0，xk=xk）。这是可能的，例如使用1 2jj−1j包括以下步骤：• 在线性数量的更新中，将x1设为1，到0：让ik成为状态1中最接近i1的自动机更新所有的自动机在从ik到i1的有向路径.如果k= 1，那么这只会传播JN1在C1中从j到n1的每个自动机上的状态1。如果k= 2，则它传播在C 2中从j到n 2的每个自动机上的状态1，然后在C 1中从1到n1。在第二种情况下，我们需要确保x1（= xo）在1它的更新，但这是因为x1=0和x2 =1，因此fo（x）= 1，到O被更新的时候因此，这些第一次更新集i1到1.要完成，如果x2/= 0（因此xn2= 1）然后更新C2的所有自动机从i1（= 0）到i2。 当o被更新时，fo（x）= 1 <$1= 0，因此值0按需传播。• 在二次更新中，将C1设置为交替配置其中x1= 1，即 设C1为11（01）n1/2−1，如果n1为偶数，设C 1为0（01）（n1−1）/2如果n1是奇数。 这可以通过以下方式实现：·对于j=n1至2，d0：·将C1的自动机从1更新到j100110000001}{1}|{2{1}{2}}01001112A. Alcolei等人/理论计算机科学电子笔记326（2016）3⊕n2Jn1 阿克斯n1 =xJj+1n22Jj+1Jn1n2−−J−Jn1n2n1n2n2n22（一）−→(ii)−→见图4。引理3.2的一个例子，具有（4， 4）正-BADC，从配置（0000， 0001）到配置（0110， 0011）。该算法分两步工作：首先将B设置为完全交替的配置，然后根据其目标状态更新每个自动机·将C2的自动机从2更新为n2在上述算法中，以下不变量成立：在每次迭代之后，x1[n1，j]=（10）（n1−j）/2 和x2=x1=xo，因此fo（x）=x121x1= x1。实 际 上，我们从x1= 1和x2= 0开 始 ，第一次迭代x12 = xo=1 0=1。 然后，对于第j次迭代，我们从x1[n，j+ 1] =（10）n1−j+1开始，f（x）=x1，所以我们结束了12oj+1其中x1=xn=xo=x1所以x1[n1，j]=（10）（n1-j）/2.• 类似地，强制C2以二次更新的方式交替（同时保留C1中的交替配置）：· 对于j=n2− 1 to 2，· 将C2的自动机从1更新为j· 将C1的自动机从n1更新为2在每次迭代之后，以下不变量保持不变：x2不变，x1=x2=x0，f0（x）/=x0，且ndx1[2，n2]和ndx2[n2，j]是交替的。 前两个语句是指令的直接翻译。 最后两个需要不变的假设。通过前面的一点，所有的不变量在进入之前都得到了满足。循环. 因此，在更新后，xo1和xo1=x2. 因此，在其更新x2=xo2j+1 （因此x2[n2，j]是一个迭代），并在相反的顺序使它交替。这也恢复了xofo（x）由于i1的状态已经随着C1的更新而切换，关于i2 一直保持不变。•在前两个步骤结束时，系统处于这样的配置中，fk（x）=xk，对除i1和i2之外的所有自动机ik。 最后一jjj22要达到完全交替的配置-其中fi（x）=xi，因此，除了o-之外的每个自动机i都以相反的顺序更新C1和C2（从n1，相应地n2，到2），然后更新中央自动机o。这需要线性数量的更新。因此，整个序列需要二次更新，并导致以下交替配置之一·（0（10））n112、0（10）n212） 如果n1和n2是奇数，n1·（（10）2，1（01）n212 如果n1是偶数而n2是奇数，010000011000110110110XX=2A. Alcolei等人/理论计算机科学电子笔记326（2016）313·（（01）2，（01）2）如果n1和n2是偶数，n1−1n2·（1）（01）2 ，（10）2）如果n1是奇数，n2是偶数。(ii)设x表示所得到的交替配置，则任何配置xJ14A. Alcolei等人/理论计算机科学电子笔记326（2016）3JJJJKJKJJ22J其中至少一个自动机ik处于稳定状态（即，使得xJk=fk（xJ）），j j j从x可到达。实际上，xo=fo（x），并且对于所有ii=o，xi=fi（x），因此在线性数量的更新中，我们可以从配置x移动到配置x∈，其中x∈o=xJo，x<$i=fi（x<$）对于所有i∈/{ik，o}。 这是通过以下方式实现的说明：· 如果ik 0且xJ0/=x0·将o和自动机从nk更新到C k中的j。然后，从x中获取x是很简单的：在必要的时候，我们只需要切换自动机的状态· 对于j=n1到2（在C1中）：如果x≠1/=XJ1，则更新子i1;· 对于j=n2to2（在C2中）：如果x≠2，则更新automatoni2XJ2;· 更新自动机ik。j j j这些更新的日期是正确的，因为对于lli∈/{ij，o}，ifx∈ixJ，则xJ=xi=我我fi（x_i），其中h是i的up日期返回的值。然后，通过定义如果x是0，则自动机0已经具有装配状态。最后，根据ij的定义，xJk=fk（xJ），这是fi在所有其他自动机J J已更新。第二个序列需要线性数量的步骤，因此整个序列仍然是二次的。 这个界限是紧的，因为从配置x=（10n1−1， 10n2−1）到一个配置xJ，其中xJi=fi（xJ），对于所有自动机i/=o（例如，配置xJ=（0（10）n1−1，0（01）n2−1，如果m和n是奇数）至少需要<$n1j+n2j=n1（n1−1）+n2（n2−1）更新，在θ（（n1+n2）2）中。j=112 2 2□备注3.3注意，如果允许同步转换，则每个配置都可以从任何不稳定配置到达。实际上，上述算法表明，如果目标配置不是不可达的，则它是立即的，但它也告诉我们，如果x是不可实现的，仍然可以实现配置x∈ C=xC1−{o}，o o1o2 1 2121 2因为在fo（x）=（x）n1（x）n2=xn1xn2=xn1xn2=xn1xn2=fo（xo）=xo=xo（weasloganBpositi ve），因此x不是不可达的。则对于C1−{o}的每一个自动机i1，f1（x）=f1（xC1−{o}）=（xC1−{o}）1=j j jj−1x1 1i1j−1=fj（x1）=xj−1，因此C1−{o}的同步更新改变了配置。系统从x到x的比率。引理3.4在BAN N中，如果i和j是两个自动机，使得存在从i到j的路径，则对于任何配置x，使得i在x中不稳定，存在从x可达的配置xJ，使得j在x j中不稳定。证据这个证明是基于这样一个事实，即在一个BAN中，使一个稳定的自动机变得不稳定可以简单地通过切换它的一个传入邻居的状态来实现（因为自动机的状态取决于它的传入邻居在状态1中的数量的奇偶性假设i和j是引理3.4中描述的两个自动机，设p = i0，i1，...， IkA. Alcolei等人/理论计算机科学电子笔记326（2016）315⊕是从i=i0到j=ik的最短路径（在N的交互图中），并且让il表示p中最后一个不稳定的自动机。然后沿着p从il更新到ik−1（因此，如果l=k，即如果j不稳定，则不会发生任何事情）将导致j不稳定的配置。从上面的评论中可以看出这一点唯一的微妙之处是路径的选择，它必须确保一个自动机的更新只会影响路径上的下一个自动机，而不会影响它后面的自动机，如果一个自动机采取最短路径，这是真的□把这些东西放在一起，我们现在可以描述定理3.1的证明背后的算法：证据 设B是BANN中大小大于3的诱导BADC，设x和XJ分别为定理3.1中描述的初始配置和目标配置。 配置x是不稳定的，因此，通过引理3.4，有可能从x到配置y，其中一个B的自动机，因此B， 并不稳定。然后，使用引理3.2和3.4，我们声称可以将B之外的每个自动机i的状态设置为其在xJ中的值，同时保持B处于不稳定的配置。其思想如下：设i是一个不在B中的自动机，且p = i0i1. ik是从B到i k = i的最短路径（在N的交互图中）。然后，应用引理3.2的算法，我们知道如何得到i0不稳定的配置，因此，使用引理3.4的算法，我们知道如何得到i不稳定的配置从这个配置中，我们可以设置i的状态如果有必要，通过更新i，将xJ I转换为X Ji因此，如果我们能够保证这个过程保持B中的不稳定性，那么我们可以在B之外的每个自动机上重复使用它，以达到B不稳定的配置，并且B之外的所有自动机都处于xJ指定的状态。一旦这样做了，我们只需要将B设置为它的正确值以达到xJ，因为B是不稳定的，这可以通过使用引理3.2的算法来完成。事实上，将B之外的自动机设置为它们在xJ中的状态是不可能的任何顺序。事实上，引理3.4的算法需要切换B之外的某个自动机的状态（即沿着从B到要建立的自动机的路径的那个自动机）。因此，我们需要保证已经处理过的自动机在处理另一个自动机时不会再次切换。确保这一点的一种方法是计算根B的宽度优先搜索树，并按照树从叶子到根的顺序处理自动机，使用树的分支作为从B到要处理的自动机的路径。图5中给出了这种排序的示例。此外，在更新序列的末尾使用引理3.2要求xJ到B的限制对于B来说不是不可达的（即对于B来说，被看作是一个-BADC，其局部转移函数由xJ中的周围环境固定）。如果不是这样的话，我们就必须使用引理3.2的第二步证明中使用的同样的技巧来解决这个问题-设i是N的自动机使得fi（x，J）=xJi（i存在，因为xJ是可到达的），我16A. Alcolei等人/理论计算机科学电子笔记326（2016）3我J910145BADC1381612421137图五、使用广度优先树的更新顺序示例设p = i0. ik是从i = i0到B的最短路径。然后我们首先得到配置x∈ su c h，使得（i）x∈j=xJj，如果j∈/p，（ii）ik（∈B）是su c h，使得x∈B的限制对于B是可实现的，以及（iii）p中的自组织的状态values是“alternating”在这样的条件下，很容易从xj到xJ：one只需要设置p备份。如条件（iii）中所述，p−{i0}中的每个自动机将能够在必要时依次切换ch状态，那么，最后，如果i0不是状态xJi0中的lready它仍然能够切换到正确的状态，因为假设fi（XJ）=XJi。所描述的配置x可以通过采用第k次迭代，x∈k，或：(i) x0=xJ(ii) 对于l>0，x<$l由y归纳定义：x<$l=x<$l−1，对于llj∈/{il−1，il}，x<$l=xJ，xli−1 是fi的解Æ−1J J（xl）=xli−1伊鲁伊河最后，为了总结上面的证明，我们仍然需要精确使用引理3.4中的算法的方式，以确保B的不稳定性被B之外的更新所保持。设z0为当前配置，设p = i0，.，ik是从B到自动机上安装。此外，设ji0是i0在B中的影响者.通过假设，B在z中是不稳定的，因此可以使用引理3.2将N置于配置z0中，其中i0是不稳定的，使得：z0=ii（z0i1）iiJ1是i0的一个输入者（i1∈I（i0）） 。i ∈f（z0{i0，i1}）ifi不是i（i∈/I（i））的不等式010实际上，我们只能保证这是可能的，如果B有一个大小至少为3的循环，这使得能够要求第三个自动机（与i0和j不同）在z0中稳定，使z0对B可达。从这里可以开始应用引理3.4：设il是p中最后一个不稳定的自动机。 如果l≤1，则开始更新p1JA. Alcolei等人/理论计算机科学电子笔记326（2016）317∈120JJJJ10JJJJ我0我0我我从i1到i1。这使得N处于z1的构型，使得B不稳定。事实上：• 或者什么都没有发生（l>1），所以B仍然是不稳定的（因为i0在z0中是不稳定的）。• 或者自动机i1是唯一更新的，因此：I1(i) 如果我∈I（i），则z1 = z0 =f（z0 ）=f（z1），所以j在z1中是不稳定的;(ii) 如果i1/I（i0），则i0的邻域没有改变，因此i0仍然不稳定在z1中。• 或者自动机i0和i1都已更新，因此：(i) 如果i0∈/I（i0）（i0没有自循环），并且如果i1∈I（i0），则i0仍然是不稳定的（因为它已经改变，并且它的奇数个传入邻居也已经改变(ii) 如果i∈/I（i），则as先前z1=z0=f（z0{i0，i1}）=f（z1）且ndsoj为z1不稳定;(iii) 如果i0∈I（i0），则i0不是j的影响者（因为B是大小为3的诱导BADC，并且j已被选择为i0的不同于i 0的前驱），因此f（z0{i1}）=f（z0{i0，i1}），所以z1=f（z0{i0，i1}），这意味着如前所述，j是j jjjz1不稳定。现在，设lJ= max（2，l），lJ是p在z 1中不稳定的最后一个自动机。然后，再一次，B在z1中是不稳定的，所以我们可以使用引理3.2来达到配置z2，使得z2=f（z1{i∈′，.，in−1}）andz2=z1，对于alli∈/B。更重要的是，由于pwaschosen要得到一条最短路径，在B中没有自动机的索引大于自动机的索引2在P。所以p的最后一个在z中不稳定的自动机仍然是il′。因此，我们可以完成引理3.4的算法（通过沿着p从il′到in−1更新自动机），并确保这会导致in−1不稳定的配置。 我们也知道，在这种情况下，B是不稳定的，因为i0具有状态fi0 （z1{i∈′，.，in−1}）。这最后一句话结束了定理3.1的证明。□算法复杂度上述算法在最差情况下是二次的然而，它的复杂性在很大程度上取决于网络的结构和/或最终配置xJ。例如，如果N中的每一个自动机都与一个大小大于3的诱导BADC的中心节点有界距离，那么这个算法在n中是线性的。类似地，由于沿着路径所需的遍数取决于沿着该路径在xJ中的交替状态（即，01或10个模式）的数量，因此如果该数量在任何路径中小于常数，则算法也将以线性时间运行。当xJ是N的不动点时尤其如此，因此每个瞬态配置都可以在线性数量的更新中达到每个稳定状态最后，我们需要指出的事实是，该算法并不总是提供最有效的更新序列（例如，它不考虑起始配置），因此该算法的复杂性只是两个配置之间最短路径长度然而，在这方面，18A. Alcolei等人/理论计算机科学电子笔记326（2016）3我 i=1我让我们注意到，这个界限有时是可以达到的，比如当一个人在一个大小为n的正向BADC中从配置10n-1移动到配置（10）n/2时。对01模式的这些考虑与[13]中为单调情况定义的表达性固定点和不可达配置根据定义，如果一个模式的配置x在与该模式相关联的转换图中没有传出弧但有自环，则该配置x是该模式的固定点。在异步更新模式中，这意味着对于V中的所有i，fi（x）= xi。因此，在一个固定点上，自动机沿着一条裸路径的状态完全由这条裸路径的头部决定。这导致了以下关于可能的固定点的数量的界限，这与作品集有关[1，6，7]。命题3.5在任何BAN N中，异步模式A中的最大不动点数目是2 k，其中k是自动机i的数目，使得πi的长度为0（即i是N的某个交互图中的“交点”）。证据只需注意到，配置x在A中是稳定的，只有当沿着裸路径的每个自动机在x中共享相同的状态值。换句话说，x完全由N的交点的状态决定。□这个界限是粗略的，我们相信，它是可能降低网络的子类。然而，如果我们将网络的收缩定义为通过移除任何其传入最大裸路πi的长度大于1的自动机i并将变量xi替换为与πi在其余局部函数中的头，则任何其收缩导致平凡网络{fi（x）=xi}i∈V的BAN都达到2k个不动点的界另外，请注意，在异步模式下，网络N={fi}n的不动点恰好是反向网络i=1NR={f R}n定义为f R（x）= fi（xi）。 N和N R是同一类型，因此N型的最大固定点数也是它的最大值无法访问的配置数量。此外，这意味着，如果给定类型的所有网络在行为上同构，则不可达的定值和固定点的数量将相等。 这些言论将通过下一节中介绍的花形链和环链的ATG的描述来说明。第4章对一些特定的BAN的研究我们现在给出两种特殊类型的BAN的完整特征：B-BA花和B-BA链。对于这两种类型的BAN中的每一种，我们描述了它们的行为同构类，并给出了它们的固定点和不稳定配置的数量。这说明了第3节的结果，并通过在BAN的交互图上使用重写引入了计算同构类的
我的内容管理
展开
