不可逆元胞自动机特性及模式分类应用

理论计算机科学电子笔记252（2009）181-203www.elsevier.com/locate/entcs单圈元胞自动机的特征及其在模式分类Sukanya Mukherjee2Nazma Naskar3孟加拉工程和科学大学信息技术系，希布普尔印度西孟加拉邦豪拉，邮编711103比普拉湾Sikdar4孟加拉工程与科学大学计算机科学技术系摘要具有多个吸引子的不可逆元胞自动机是元胞自动机研究的一个热点。这样的CA的特性是必要的CA为不同的应用程序设计的解决方案。本工作探讨CA吸引子的基本性质，对1维元胞自动机与点状态（单长度周期吸引子）的表征。可达树的概念被引入到这样的表征。它能够识别CA的伪穷举位（PE位），定义其点状态。已经开发了一个理论框架来设计用于合成具有特定PE位集的单长度循环多吸引子CA的方案。 它还导致在一个线性时间的解决方案，同时合成CA的给定集合的吸引子和它的PE位。实验结果表明，提出的元胞自动机综合方案在设计适用于广泛应用的高效模式分类器方面是最有效的。保留字：元胞自动机，吸引子，伪穷举位，可达树，模式分类器。1介绍元胞自动机（CA）的引入是历史上的一个重要发展，提供了具体计算机的抽象模型[20]。CA的概念是在20世纪50年代初由J.冯·诺依曼和斯坦·乌拉姆[21]。研究人员曾试图1电子邮件：sukanta@it.becs.ac.in2 电子邮件地址：sukanyaiem@gmail.com3电子邮件：nazmapreeti@yahoo.co.in4 电子邮件地址：biplab@cs.becs.ac.in5这项研究工作得到了赞助的元胞自动机研究项目的支持，孟加拉工程和科学大学，Shibpur，印度-711103。1571-0661 © 2009 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2009.09.021182S. Das等人/理论计算机科学电子笔记252（2009）181查看CA的简化结构，以进行表征。针对结构简化的工作是[1，2，4，5]。在20世纪80年代早期，Stephen Wolfram [26]详细研究了一个简单的一维元胞自动机家族，可以模拟复杂的细胞[15，22，23，24，25]。CA结构被看作是一个离散的晶格的两个状态，每个细胞与3个邻居的依赖性（自我，左，右邻居）。这种结构吸引了大量在不同领域工作的研究人员，一类特殊的一维CA，称为线性/加性CA，已经获得了主要的关注[3]。在[3]中开发的理论框架针对非均匀线性/加性CA的表征。在表征CA状态空间时，研究人员确定了一组CA状态，相邻状态在动态演化过程中渐近接近[27]。这组状态，称为CA状态空间的吸引子，与其相邻的状态形成吸引盆。这种在状态空间中具有多个吸引子的CA在模式识别、模式分类、联想记忆设计、查询处理等应用中具有重要意义[3、11、12、13、14]。具有多个单长度循环吸引子（点状态）的CA的表征在现实生活应用的成本效益解决方案中受到特别关注与线性/加性CA中此类吸引子的识别以及单长度循环多吸引子线性/加性CA的合成相关的问题在[3，12，14]中得到了还提出了用于这种识别的基于图的解决方案[16，19]。然而，单长度循环吸引子的特征以及具有特定单长度循环吸引子集合的CA的合成还有待探索。在这种情况下，我们集中在一类特定的一维非线性细胞自动机的单长度周期吸引子的特征。我们解释plore的CA吸引子，使这种特性的基本属性。可达性树的引入为CA的吸引子的识别以及其PE（伪穷举）位的定义提供了理论基础。已经开发了一个理论框架，有效地利用该理论框架来设计用于合成具有特定PE位集并且仅具有单长度循环吸引子的CA的方案。所提出的综合方案被认为是有效的，而设计的CA为标准应用的模式分类器。下一节介绍与当前工作相关的元胞自动机系统。第三节介绍了可达树的概念和CA状态空间刻画的理论基础。一些线性时间算法/解决方案，如吸引子数量的计算、PE位的识别等，也将在本节中报告。在第4节中报告了具有特定PE位集的单长度循环多吸引子CA的合成。在第5节中，我们报告了按照第4节中设计的综合方案设计的模式分类器。S. Das等人/理论计算机科学电子笔记252（2009）181183在外层电池i−1（法国法郎）fi在外层细胞i+1（法国法郎）在外层小区i（法国法郎）f1在外层电池1（法国法郎）0nn+1个1. . .. . .零边界. . .组合逻辑电路. . .零边界Fig. 1. 带FF的边界CA与组合逻辑电路2元胞自动机元胞自动机（CA）由许多以下列形式组织的单元组成： 格子。它在离散的空间和时间中演化。CA的每个单元在时间t存储一个离散变量，该变量指的是单元的当前状态。单元在（t+ 1）处的下一个状态是由其状态和其邻居在时间t处的状态确定的。在目前的工作中，我们集中在3-邻域（自，左，右邻居）CA，其中CA细胞有两个状态- 0或1。这种CA的第i个单元的下一个状态是（一）St+1=fi（St、St、St）ii−1fi是下一个状态函数;St，St和Sti i+1是左派的现状i−1i一期+1在时间t处的第i个CA小区的邻居、自身和右邻居。其单元在时间t的状态St（St，St，···，St）的集合是当前1 2N一个n-cellCA的状态，它的下一个状态是（二）St+1=（f1（St，St，St），f2（St，St，St），···，fn（St，St，St ））0121 2 3n−1n n+1如果St=StSt=St，则CA是周期性边界CA。 上如果St=St= 0（null），则CA为空边界。 图1显示了0n +1两状态3邻域零边界CA的示意图。 每个CA细胞用存储器元件和实现下一状态函数（f1）的组合逻辑来实现在目前的工作中，我们专注于零边界CA。第i个CA单元的下一个状态函数（组合逻辑）可以以真值表（表1）的形式表示。8个输出的十进制等价物称为 在两状态3邻域CA中，总共可以有28（256）条规则。在表1中示出了三个这样的规则90、150和75。 表的第一行列出了在时间t时第（i-1）、第i和第（i+ 1）个单元的当前状态的可能的2× 3（8）种组合。 最后三行表示下一个第i个单元在（t+1）处的状态，对于其当前状态的不同组合，邻居，分别形成规则90、150和75。在256条规则中，有14条被称为线性/加法规则[3]，它们只使用XOR/XNOR逻辑。规则最小项（RMT）：从切换理论的观点来看，当前状态的组合（如表1的第一行所示）可以被视为最小项3-变量（St，St，St）的项）切换功能。 因此，每列i−1i一期+1fn在外层小区n（法国法郎）184S. Das等人/理论计算机科学电子笔记252（2009）181表1的第一行被称为规则最小项（RMT）。 列011是第三个RMT。 对应于此RMT的下一个状态是规则90的1S. Das等人/理论计算机科学电子笔记252（2009）1811851301064911214158251137表1规则90、150和75的真值表现状： 111 110 101 100011 010 001000（RMT）（七）（六）（五）（四）（三）（二）（一）（0）(i)下一个状态：0101101090(ii)下一个状态：10010110150(iii)下一个状态：0100101175注：RMT代表规则最小期限。第3/4/ 5行上标注的值0/1表示三变量开关功能的输出图二. 可逆CA的状态转换105， 177， 170， 75>第75条，第150条为0。在这项工作中报告的表征是基于对CA规则的RMT的分析。定义2.1确定CA的单元格的规则集R=称为规则向量。定义2.2如果R1=R2=···=Rn，则CA是一致CA，否则它是非均匀或混合CA。定义2.3如果规则向量R的所有Ris（i= 1， 2，···，n）都是线性/可加的，则CA被称为线性/可加CA，否则CA是非线性CA。生成的状态序列（状态转换）在其演化（随时间）期间指导CA行为。CA的状态转换图（图2和图3）可以包含循环和非循环状态（如果状态位于循环中，则称为循环;图2的状态），并且基于此，CA可以被分类为可逆或不可逆CA。在可逆CA中，每个CA状态在一定数量的时间步长后重复（图2）。因此，可逆CA的所有状态都可以从其他一些状态到达，其中每个状态只有一个前任。 另一方面，在不可逆CA（图3）中，存在一些不可达状态。这些国家186S. Das等人/理论计算机科学电子笔记252（2009）181115 28 73不能从CA的任何其他状态访问。此外，不可逆CA的一些状态有一个以上的前身[17，18]。 图3的状态5和13是不可达状态，而15和7具有多于一个前驱。不可逆CA形式Garden的不可达状态伊登 图3的周期7→ 3→ 11→ 7和15→15是CA< 105，177，171，75>。15是一个单长周期吸引子（点状态）。图三. 不可逆CA的状态转换105，177，171，75><伪穷举（PE）位：一组m位可以唯一地识别n-cellCA的2m个牵引器，其中m≤n。这些穷举地出现在CA的2m吸引子的集合中，并且被称为PE（伪穷举）位。在图4中，有四个吸引子- 2（0010）、12（1100）、13（1101）和3（0011）。吸引子的最低有效位10、00、01和11可以唯一地识别这些吸引子，称为PE位。CA的PE位的识别在为应用开发CA模型时减少了计算开销以及存储开销。本文主要研究单长圈吸引子CA及其PE位的刻画。以下各节报告了这种表征。3CA吸引子的特征本节报告CA吸引子的性质，以探索不可逆CA的单长度循环吸引子（点态）。拟议的表征是S1S2S3S4见图4。 具有规则向量10、 69、 204、 68的CA的状态转换>可以考虑三比特窗口来获得CA的下一个状态[8]。如果对 于 h单元的宽度为（ bi−1bibi+1）， bi=0/1，则对于（i+1）h 单元的宽度为（bibi+10）或（bibi+11）。在这种情况下，如果CAcell changsistata 在计算CA的下一个状态时，Ri和Ri+1的RMT之间的关系示于表2中。图7是CA<8， 112， 44， 68>的可达性树。的RMTCA规则在表3中注明。在级别i处的节点内的十进制数表示CA单元规则Ri+1的RMT，基于该规则，单元（i+1）可以改变其状态。注意我们遵循0-边或1-边的规则的RMT1（六）S. Das等人/理论计算机科学电子笔记252（2009）1811890（0，1）40，1，0、11（三）权重= 8四、0G040（0）0，21 0（二）（四）四、六0（0，1）权重= 80，1，3表3RMCAT 8， 112， 44， 68>单元格规则RMT 111 110 101 100 011 010 001 000（七）（六）（五）（四）（三）（二）（一）（0）第一细胞DDDD10008二小区01110000112T细胞0010110044F细胞D1D0D1D068识别比特一重量=B识别比特权重= 2（0，10）D1（二、三） 权重= 2识别比特1.2.1 = 2（权重= 1HI1（6）重量= 1M权重= 1O P Q RY见图8。 吸引子的可达树在括号里。例如，图7的根节点（级别0）由RMT0、1、2和3构成，因为小区1（规则00001000）可以在RMT0、1、2和3中的任何一个之后改变其状态。由于小区1的左邻居的状态总是0，RMT4、5、6和7是不关心小区1的。 从图7中可以明显看出，树中有12个可能的边序列加州16个州中有12个州可达，其余的不可达。可达性树识别CA的所有可达状态，包括吸引子。图7的树也可以修改为只显示吸引子。由于一个单元格规则的所有RMT都不能产生吸引子，因此这些（无意义的）RMT被从可达树中删除。例如，RMT2（010）为0意味着它是无关紧要的（它不能产生吸引子）。图8所示的树对应于CA8， 112， 44， 68>。它是从图7导出的，只指向吸引子。利用具有形成吸引子的潜力的RMT来构造图8的节点。它显示了12个可达状态C1 （六）权重= 460（0）190S. Das等人/理论计算机科学电子笔记252（2009）181中的5个（O，P，Q，R和Y）是吸引子。S. Das等人/理论计算机科学电子笔记252（2009）1811910103.2吸引子集在前面的小节中，修改后的可达树可以用来描述CA的吸引子集。为了找到CA的吸引子的数量，我们需要从左到右扫描CA（R），并虚拟地形成可达性树。树中叶子的数量表示CA的吸引子的数量。权重与每个子树相关联（图8），表示其生成吸引子的能力。算法1 CalNoOfAttractor输入：（n-单元CA）。输出：CA的吸引子数量。步骤1：如果任何规则不持有属性1，则报告吸引子的数量为0并返回。步骤2：设S0和S1是两组RMTs，能够产生吸引子，第一个细胞规则，其中S 0的RMTs为0，S1为1。如果S0=/φ，则对于左subt，2n−1。如果s1φ，将右子树的权重设置为2 n−1。步骤3：对于i = 2到n对于每个RMT集合{考虑表2和Ri，为可达性树的下一级节点确定能够生成吸引子的RMT s。基于下一个状态值将这些RMT分配到集合SJ和Sj中0 1分别为0和1如果SJφ，将新左子树的权重设置为子树权重的一半考虑一下如果SJφ，将新右子树的权重设置为子树权重的一半考虑一下}如果有重复的集合（子树），只考虑一个，并将其权重分配为所有重复集合的总和第4步：将计算的权重相加，并将其报告为CA的吸引子数量。复杂度：算法的复杂度取决于n和RMT集合的数量。由于RMT的数量为8，因此RMT的最大可能集合数量也是固定的（≤8）。所以复杂度是O（n）。示例3.1本示例说明了算法1的步骤。让我们考虑CA8，112，44，68>（表3）是算法1的输入。CA的每个规则都维护属性1（步骤1）和S0={ 0，1}S1 ={3}（步骤2）。以来S0/=φ和S1/=φ，这两个子树都可以生成吸引子。由子树指示的吸引子的最大可能数量是24 - 1 = 8（子树）。在步骤3中，确定吸引子的可达性树的下一个节点节点为{0，1}和{6}。对于第一个节点，也就是第一个集合，SJ={ 0， 1}192S. Das等人/理论计算机科学电子笔记252（2009）18112而SJ=φ。因此，右子树不能指向吸引子。的左子树指出了左子树的吸引子和权的存在性8=4。另一方面，节点{6}只能生成其右子子树（SJ=φ且SJ={ 6}）。因此，其右子树的权重为8= 4。012该过程将继续，直到遇到CA的最后一个规则 在下一个级别中，识别两个节点-{ 0，1，2，3 }和{ 4 }。第一个节点有两个子节点，但节点{4}有一个子节点，相应地计算权重（2，2和2）。在处理最后一条规则后，5个子树，每个子树有一个节点（权重= 1）。然而，图8的两个节点0和Y是相同的，因为两者都是从最后一个规则（规则68）的RMT这些被替换为分配权重= 2的单个值。最后，权重之和2 + 1 + 1 +1 = 5定义吸引子的数量（步骤4）。3.3PE位的识别本小节报告了从一组n位吸引子中识别K位位置的方案，其中K≤n，该方案可以唯一地识别所有吸引子。这K个比特可以充当CA的伪穷举比特。所提出的方案探索了CA的修改后的可达性树，定义在第3.1节中。以下示例说明了该方案。例3.2考虑图8所示的可达性树的根节点。 它有两棵树。左子树包含4个吸引子（O，P，Q和R），而右子树只包含一个（Y）。从图中可以看出，以0开始的吸引子是左子树的一部分，而以1开始的吸引子（Y）是左子树的一部分。是右子树的一部分。 因此，n位CA状态的第一位（MSB）是标识位。类似地，节点D、H和I在根的左子树的吸引子之间进行区分。 因此，最低有效位也是标识位。因此，4位中的3位（第一位、第三位和第四位）可以识别CA的所有吸引子。可以注意到，最小有效的两个（第三和第四）位在吸引子集中出现。然而，3个标识位并不完全出现在所有（5）吸引子中。因此，这3个标识位不是PE位。也就是说，标识位不一定是给定吸引子集的PE定理3.3 m个n比特吸引子可以由K个比特位置来识别，其中K≤n&m≤ 2 K，并且存在r个PE比特位置集合，它们是K的子集，其中p1，p2， · ··，pr ，其中2p1+2p2+· · ·+2pr=m。证据考虑一个CA的可达性树为m吸引子。第一个节点，从根开始，有左子节点和右子节点，将吸引子集合分成两个子集。对应于该节点的位是标识位，并且可以穷举地标识两个子树（子集）。现在，对于每个子树，我们可以找到另一个标识位，将子树分成两个子子树，并且还可以穷举地标识子子树。这个过程一直持续到我们到达叶子。因此，每个吸引子都可以通过一组识别来S. Das等人/理论计算机科学电子笔记252（2009）1811931001位，以及唯一标识所有m吸引子是K，其中K≤n。现在，许多吸引子可以以这样的方式分组，即识别位的子集穷举地出现以识别该组（即子集）的所有吸引子。因此，标识位的子集是用于该特定吸引子子集的PE位。 让我们考虑一下，这些子集的数量吸引子是R。因此，2p1 + 2p2+···+2pr = m，其中pi（≤K）是第i个子集的基数. 所以才有证据。Q例如，示例3.2的5个吸引子可以由2组PE比特来标识– the first bit and third 因此，p1= 1，p2= 2。推论3.4一个n -胞元CA的吸引子的数目为2K，可以由K个比特位置来识别，其中K≤ n。证据 如果存在一组PE，则从定理3.3直接得出推论位位置，即r= 1。Q接下来，我们提出以下算法来找到CA的K个这样的标识位。该算法隐式构造吸引子的CA的可达树。如果找到具有两个孩子的节点，则对应于该节点的位被标记为标识位。算法2 FindIdentificationBits输入：（n-小区CA）。输出：标识位。步骤1：如果任何规则不包含属性1，则返回。步骤2：假设S0和S1是两组第一规则的RMT s，可以有助于吸引子的形成，其中S 0的RMTs为0，S1为1。如果S0/= φ/= S1，则标记第一位。步骤3：对于i = 2到n对于每组RMT使用表2和Ri确定有助于可达性树的下一级节点的吸引子（对于吸引子）的形成的RMT。将这些RMT分布到SJ中1.而SJ基于下一状态值0和如果SJ/= φ SJ，则标记第i位。步骤4：将标记的位报告为标识位。复杂度：算法2的复杂度取决于n和RMT集合的数量。由于RMT的数量为8，因此RMT的最大可能集合数量也是固定的（≤8）。所以复杂度是O（n）。示例3.5该示例说明了算法2的执行步骤。考虑CA <8，112，44，68>，见表3。由于所有规则都保持属性1，因此CA可能存在单长度循环吸引子（步骤1）。这里，S0={ 0，1}，S2={ 3}。因此，第一位（MSB）被标记为标识194S. Das等人/理论计算机科学电子笔记252（2009）1811001位（步骤2）。 然而，对于S0，SJ对于S1，SJ都是空的 因此第二MSB不能是标识位（步骤3）。同样，可以发现，第三第四位是标识位。在下一小节中，算法2被修改为找到CA的伪穷举位，如果有的话，以识别所有吸引子。3.4特定PE位的 CA合成本小节提出了一个多吸引CA的综合方案，基于3.3节中报告的理论框架。以下算法描述了所提出的合成方案。算法3 GeneralizedMACASynwithPE输入：n（CA大小），K（PE比特）。输出：CA（规则向量）。步骤1：随机识别被视为PE比特的K比特。步骤2：假设S0和S1是第一小区的两组RMT，其中如果RMT有助于形成吸引子，则S0为0，S1的RMT为1。如果第一位是标识位，则随机设置RMT，使得S0/= φ/= S1。否则，设置RMTs，使S0/= φ（S1/= φ）但S1 = φ（S0 = φ）。步骤3：对于i = 2到n对于每组RMT确定可达性树的下一级节点的RMT，如下所示：表2.将这些RMT分配到SJ和SJ中，其中SJ的RMT为0，SJ是0 1 0 1如果RMT被选择用于生成吸引子，则为1如果第i位是标识位，则随机设置RMTs，使得SJφSJ.因此，如果R MT满足Sj=fφ（Sj = φ），则SJ=φ（SJ=φ）。0 1 1 0步骤4：为每个单元格规则设置未填充的RMT（如果有的话），以便不会有额外的位被填充。被视为PE位。步骤5：报告具有K个PE比特的CA。复杂度：算法3在步骤3中使用了一个依赖于n的主循环。集合的最大数量是恒定的。也就是说，算法2的执行时间仅取决于n和RMT集合的数量。因此，上述算法的复杂度显然是O（n）。虽然算法3的目标是合成具有单长度循环吸引子的CA，但是从算法3合成的CA也可以具有多长度循环吸引子。该计划，确保合成的CA只有单一长度的周期吸引子的S. Das等人/理论计算机科学电子笔记252（2009）181195报告。196S. Das等人/理论计算机科学电子笔记252（2009）1814单圈吸引子CA前面的部分报告了CA吸引子及其PE位的表征。本节进一步表征了CA的CA靶向合成，该CA仅具有带有特定PE位的单长度循环吸引子。为了便于表征，我们接下来引入RMT序列（RS）的概念定义4.1在n单元CA的可达性树中遍历以达到可达状态的边是从RMTsx1x2···xn>的序列导出的。<它是RMT序列或RS用于可达状态。例如，考虑表3的4单元CA8， 112， 44， 68>。相应的可达性树如图所示第七章RS3640>导出状态1100，其中3、6、4和0是对应于R1（8）、R2（112）、R3(44)和R4（68）。如果一个状态可以从多个状态到达，比如3个状态，则3个RS指向可达状态。另一方面，不可达状态不能关联RS。与可达状态及其下一状态相关联的两个RS是相关的。为了找到关系，我们将8个RMT分为两组-RMT0和RMT1，其中RMT0={ 0，1，4，5}，RMT1={ 2，3，6，7}。 RMT0的RMT为0RMT1的RMT s和RMT s均为1，而RMTs有助于形成单长圈吸引子（第3节的属性1）。假设x1x2···xn>是n个小区CA状态的RMT<也就是说，xi是Ri的RMT。现在，考虑RMT xi不遵循性质1并且xi∈RMT0。也就是说，RMT xi的下一个状态是1。RMTxi−1RMTxi+1可以是0/1。让我们考虑y1y2···yn>是下一个状态的RS<因此，yi可以是010、011、110或111同样地，如果RMT xi遵循性质1，则可能的yi是0、1、2或3。 这些情况见表4。现在，如果xi∈RMT1，用类似的逻辑，我们得到表5。因此，利用表4和表5，可以确定给定RS（RSt）的下一个RS（RSt+1）定义4.2[6]两个RMT是等价的，如果两者都导致相同的一组可达性树下一级的RMT例如，RMT0和4是等价的，因为对于可达性树的下一级，这两个RMT都导致相同的有效RMT集合{000=0，001=1}（表2）。类似地，RMTs 1 5、2 6和3 7是等效的。4.1多长度周期本节的动机是设计一个CA只有单一长度的周期吸引子。下面的定理确定了多重长度循环形成的原因。定理4.3n-胞元CA的一组状态属于长度为l的循环，其中l≥2，若Ri的RMTsr1，r2不遵循性质1且r1∈RMT0&r2∈RMT1，则RJ∈RMT0RJ∈RMT1或RJ，RJ&∈RMT0/RMT1，1 2 1 2其中RJ，RJ是Ri+1的RMT s，RJ（RJ）是从r1（r2）导出的。1 2 1 2S. Das等人/理论计算机科学电子笔记252（2009）181197表4RStRSt+1（RM Txi∈RM T0）的RM Ts之间的关系RStRSt+1RMTxi−1RMTxi={ 0，1，4，5}RMTxi+1RMTyi00111111010123670011000001010145表5RStRSt+1（RM Txi∈RM T1）的RM Ts之间的关系RStRSt+1RMTxi−1RMTxi={ 2，3，6，7}RMTxi+1RMTyi00110000010101450011111101012367以下示例说明CA如何在其状态转换期间形成多长度循环（长度为3）。例4.4让我们考虑图4.4的4-小区CA5， 73， 200， 80>。第九章CA小区规则的RMT在表6中注明。对于第一个单元（R1= 5），RMT0和3不保持属性1，并且198S. Das等人/理论计算机科学电子笔记252（2009）181来自不同的集合（RMT0RMT1）。之间S. Das等人/理论计算机科学电子笔记252（2009）181199表6CA5，73，200，80>小区规则的RMTRMT 111 110 101 100 011 010 001 000（七）（六）（五）（四）（三）（二）（一）（0）第一细胞DDDD01015二小区0100100173T细胞11001000200F细胞D1D1D0D08040124241224005252591 1376见图9。 具有规则向量5、 73、 200、 80的CA的状态转换><考虑它们用于下一级的连续RMT，RMT0和7，属于不同集合的RMTs 0和7不遵循性质1，而RMTs 1和6遵循性质1。 对于R2（73），RMT为0，7和2不遵循性质1，其中RMT7，2∈RMT1且RMT0∈RMT0。现在，如果取RMTs 0和7，则它们的后续RMTs遵循性质1，但它们来自不同的集合（RMT0RMT1）。它违反了形成多长度循环的规则。 当考虑RMT0和2时，它们的后续RMT如下：性质1来自同一集合（RMT0，2∈RMT0），并有助于形成多长度圈。 因此，RMT1被认为是R1。R3的RMTs40和R4的RMT0遵循性质1，它们是连续的RMTs分别在RMT的第二和第三级2、6和0。现在如果我们考虑RMT序列RS13640>，则除了RMT3之外，都遵循性质1。<当计算RS2时，除了在第二位置的RMT2之外，所有都遵循性质1，其中序列的其他RMT在第一、第三和第四位置分别为1、4和0。RS3推导出0000>，其中在第一和第二位置的RMT不保持属性1，但在第三和第四位置，遵循属性1，重复RS1。<因此，循环[3640（0010）→1240（0000）→0000（1100）→3640（0010）]是由长度3组成。下一小节提供了设计一个CA只有单一长度的周期的理论框架6136414737641537761201362536 1310125281240000000012311364023652200S. Das等人/理论计算机科学电子笔记252（2009）1814.2单长周期以下定理指导识别仅具有具有指定PE位的单长度循环吸引子的CA定理4.5对于n单元CA，如果第i位是PE位，则RMT0、1、2、3或RMT4、5、6、7或Ri的所有八个RMT都遵循性质1，这取决于R i-1的RMTs，遵循性质1。证据让我们考虑一个n单元CA. 如果第一位是PE位，则0边缘 和1-在级别0处的可达性树的边缘必须具有跟随属性1的RMT。 因此，RMTs 0，1，2，3在R1处遵循性质1，第二位是PE位。如果第二位不是PE位，则在R1RMTs0或1或两者都必须遵循属性1，并且对于RMTs 2、3来说，这一点是相同的。对于单元i，如果第i位是PE-位，则Ri的RMTs以这样的方式选择，即它必须遵循属性1以表示作为PE-位的重要性，Ri-1的RMTs被考虑。 当在第i层时，RMT0、1、2、3遵循性质1，则性质1之后是RMTs 0，1或4，5或0，1，4，5（i−1）。 在同一方式，RMTs 4、5、6、7在规则Ri处计算。 RMT0，1，2，3都遵循性质1，以避免形成多长度循环。对RMT4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、197.对于不具有属性1并且来自同一个集合的水平（i-1）的RMT，连续的RMT必须随机选择（0/1）。 所以才有证据。Q定理4.6对于n-单元CA，如果第i位不是PE-位，则以这样的方式构造Ri(i) 当RMT0、1、4、5遵循特性1时，RMT2、3、6、7不遵循特性1，反之亦然，这取决于选择哪些RMT来维持特性1。Ri−1，其中第（i+ 1）位是PE位(ii) 只有两个等价的RMT遵循性质1，而其他六个RMT不遵循，这取决于哪些RMT在Ri-1处遵循性质1，其中第（i + 1）位不是PE位。证据让我们考虑一个n单元CA.如果第一位不是PE位，则RMT0、1或RMT2、3遵循属性1，其中下一位是PE位。当下一位是PE位时，则RMT0、1、2、3或RMT4、5，应遵循6、7的原则，以限制多旋回的形成。因此，第一个规则必须遵循RMT0，1或2，3。如果第二位不是PE位，则0、1、2、3中只有一个RMT遵循第一规则中的属性1。对于单元i，如果第i位不是PE位，则当第（i+1）位是PE位时，RMT0、1、4、5或RMT2、3、6、7遵循属性1规则Ri以这样的方式构造，即来自同一集合的RMTs要么遵循性质1，要么不遵循，以防止根据RMTs形成多长度循环如果第（i+ 1）位不是PE位，则在Ri处，RMT以这样的方式构造只有两个等价的RMT遵循性质1。Ri被构造成以这样的方式，来自同一集合的RMT不遵循性质1，对于其他集合，两个等价的RMT只遵循性质1，以防止多长度循环的形成，这取决于在Ri-1处满足性质1的RMT。因此