目前参与的科研项目，需要阅读的论文难度都有点大，所以开个小坑来记录一下阅读笔记，免得以后忘了还得重新读。当然，因为这些内容都是跟代数强相关的，因此我作为一个文科背景的跨专业人员，可能会有很多理解上的失误，有高手看到了，还望不吝指出并及时赐教...、

话不多说，开坑！！！！

论文题目：Efficient exhaustive listings of reversible one dimensional cellular automata

论文作者：Tim Boykett

摘要

本文关注一维细胞自动机的一个代数构造。使用的构造方法与组合结构和图论的联系变得清晰。关于唯一性和同构性的有力结果使我们能够概述用于生成可逆一维元胞自动机的详尽列表的有效算法，并计算存在的不同示例的数量。这些算法使用“有序算法”方法来避免暴力搜索的陷阱。

1.引言

没啥硬核内容。

第一段。介绍了作者自己方法的优势，点出了细胞自动机研究中存在的语言不不统一问题。本文通过摈弃原有的细胞自动机语言体系，是的本文可以通过已有的代数、组合结构和图论的工具对细胞自动机的性质进行研究。

第二段。重点介绍了可逆性计算的含义，就是能够让细胞从最终状态回复到最初状态。关注可逆性计算的好处是，可以将重要的额外结构包含进去（我猜测这里的意思是可以让细胞自动机包含更多的信息）。这与半群（可转换的）和群（转换时不可逆的）的不同是相当的【这句我理解起来可能会出错，所以直接给原文，原文是：This is comparable to the differences between semigroups (of transformations) and groups (where the transformations are invertible).】。这个额外的结构可以让人们从那些可能不可逆的样例中找出更多的对象（猜测可能是可逆对象）。并且，已有证明论证，这中可逆性对计算能力也没有任何的限制。

第三段。介绍文章结构，先从代数的某些概念出发，并提出了一些重要的性质。如：广义半中心双群（general semicentral bigoupoids）可以被表示为一个幂等的带有相关排列的半中心双群（semicentral bigoupoid），称为“lifting”。然后，我们协调代数结构并导出一个组合对象，一个矩形结构。以下各节显示组合对象是直接的等效于幂等半中心双群胚。

第四段。作者提到他们利用Pedersen的技术证明了幂等半中心双群等价于一个可逆的细胞自动机。

第五段。作者提到他们引入了代数和组合结构作为一对图的进一步模型，并证明它是等价的。重要的是，代数结构和图结构的自同构群被证明是相同的。然后，我们研究半中心双群之间的同构，准确确定两个半中心双群何时同构，并开发一种技术来计算可以从给定的幂等半中心双群中提升的不同半中心双群的数量。然后我们找到一种逐个构建半中心双群体的技术，表明我们可以使用这种技术生成所有示例。作者提到他们应用一种用于穷举生成矩形结构的电子算法。使用同构结果，我们可以计算不同的半中心双群的数量，从而计算可以导出的元胞自动机规则从那个结构。

【这个引言，基本上是翻译，第五段就是说作者做了那些努力来找出合适的算法】

2.代数结构

作者在这个部分介绍了什么是中心群和半中心双群

2.1 定义和简单的结果

群（goupoid）的定义：(2)-algebra (S, ·)，其中 ·运算时二元运算，如下图：

双群（bigroupoid）定义：当然运算也都是二元运算

群的一些性质：

引理1：

这三条性质中，第一条说明的是某些集合的笛卡尔积满足与*号运算与群等价；第二条说明如果二元运算的左右两端可以交换位置等价于左右两端元素相等；第三条则是群也是一个具有a·b·a=a的幂等半群。

定理2：

该定理说明一个有限的中心群中的元素个数一定是某个整数的平方阶。每个正整数都存在一个其平方阶的中心群。任何整数平方阶的中心群，其幂等数就是该整数。对于大于等于3的整数有其平方阶的非天然中心群。

Knuth探索了中心群的多个方面，并且发现了两个中心群的模型，一个是图模型，另一个是基于 {0,1}-矩阵的模型，这些矩阵是这些有向图的入射矩阵（incidence matrices），这些{0,1}-矩阵A由如下性质：A^2 = J, J矩阵完全由1组成。

作者还提出，穷尽所有的中心群与穷尽所有的矩阵符合如上性质是等价的。

定义3：

一个半中心双群满足如下公理：

还有如下性质：

此处，说明了如何通过一个中心群产生一个半中心双群。且半中心双群的运算符号是对称的，因此只需要关注其中的一个。通过对运算进行简单的的定义，可以定义一个左保持半中心双群，或者右保持半中心双群。这两种双群都是平凡的。【我觉得这里可以对应细胞自动机中的平凡规则】。

例2：

从例子中可以看到，定义的半中心双群Q是集合A和B的笛卡尔积，且定义的运算是封闭的。黑圆点运算，得到的结果是左元素对的左元素和右元素对的右元素组成的新元素对，这个元素对也是集合Q内的某个元素。白圆点运算的分析类似，且结果也在集合Q内。

接下来验证是否满足两条公理：

证明过程比较简单，而且隐含了幂等性。

这个样例与自然的中心群相对应，且可以被构造为“点乘”。此处的（Q,黑圆点）和（Q,白圆点）都定义了一个长方形的半群。如果一个半群是关联的（associative），其对应的半中心双群也是。而且，所有的关联半中心双群都与样例的形式一致。

引理3：

引理3说明了半中心双群的两个计算是反交换的（反交换性条件比无交换性更强），当且仅当运算两端的元素相等时，才能够做等价交换；且由此可以推出两个运算都符合幂等性，这块在样例的证明里已经体现。

简单证明：

1：(a1,b1)·(a2,b2)=(a1,b2)，

2：(a2,b2)·(a1,b1)=(a2,b1)，

当仅当a1=a2，b1=b2，即(a1,b1)=(a2,b2)时1、2式相等，且都等于(a1,b1)或者(a2,b2)，满足幂等性。

【这里的反交换，感觉有点问题，从反交换律的定义（来源：维基百科）看：

如果满足反交换律，那么a*b=-b*a，不知道怎么定义这个逆运算，也可能是我自己多想了，总之，在推理上是没问题的。】

2.2. Lifting

从任意一个半中心双群做“折叠”可以得到另一个半中心双群。这是找寻半中心双群新样本的一个方法。

命题4：

如果存在一个半中心双群，以及一个关于对应集合的置换【这里的permutation，还有排列的意思，如果翻译成这个，我感觉有点对不上】，可以通过将新的运算与原运算和置换做一个对应，得到的新的代数也是一个半中心双群。

作者还提示，一般而言，新的半中心双群与原来的半中心双群不是同构的。

【TNND，又有一个新词汇isomorphic，同构。对一个跨行的人而言太TM不友好了，同构的定义（维基百科）：

我的理解就是从A->B可行，那么从B->A也可行，且A内元素跟B内元素都是一一对应的。】

定义5：

【开始难起来了，代数要求开始变高了...TNND】

这里定义了“lifting"操作，就是将一个原有的半中心双群通过一个运算（上文提到的置换，permutation），得到一个新的半中心双群。这里提出了一个运算：平方映射，和这个平方映射的逆运算：逆平方映射。

从命题4中给出的新半中心双群中所定义的新运算看，这个平方映射恰好可以和前面的逆平方映射计算得出原有的元素，因此得到一个新运算时幂等的。而且，如果对一个被平方映射lifting所的到的半中心双群做一个基于逆平方映射的lifting，则可以得到原来的半中心双群。

【这不就是一个双射吗？所以这不是一般情况...】

作者在这里得出结论，这种lifting的操作时可逆的，且每一个半中心双群都是一个幂等的半中心双群的lifting，且其permutation（置换？排列？）都能变为平方映射的逆。

并且，作者提到在半中心双群中可以有任意的permutation作为平方映射并且任意数量的幂等，与中心群的幂等不同，中心群的幂等要求等于有限集合内元素数量的开方。

此处，作者定义了一个新的符号Symm(S)来表示集合S是对称群。

推论6：

作者这里提出，每个半中心双群都可以被唯一的表示成一个幂等的半中心双群和其对称集合上的一个permutation。相反的，当仅当permutation时平凡的时，才能给出这些幂等的半中心双群对。

将幂等lifting的过程应用到中心群中，获得一个半中心双群。定义好相关集合和运算后，可以的到下列表格：

为了更好的说明，这里用手推一下，过程如下：

引理4：

这里说的就是一个自然中心群在幂等lifting后得到的半中心双群是关联的。

2.3 关联的半中心双群

上述的等式(13)的详细推理，应该是这样：

从而得到了

引理5：

【到这个地方，section2算是搞完了，整体来说这俩部分还是不太难的。但是，篇幅才到了6/33，我真的TM了】

3.矩形结构

这一个部分举例说明了所有的半中心双群都等价于一个确定的组合结构。通过这样的等价，作者确定了这些代数结构的一些性质。这部分提及的所有半中心双群都是幂等的。

3.1. Partition

【这个名词，实在不知道咋翻译，翻译成分区也太抽象了...T_T，我觉得这里的意思跟离散数学里的那个partition差不多。】

【开始抽象起来了，md！】

这里实在是，一时半会想不清楚想表达的意思。我的理解是：这个先对S集合做平方，然后再通过P(S^2)这个定义一个S^2的幂集。下面则是这个集合里每个元素的定义。

引理6：

推论6就是给出了半中心双群和定义的组合结构之间的联系。

对于推论6的证明：

引理6定义了一个运算，可以将S^2这个集合分割成标准乘法的集合，且是可以由rectangles组成的partition。因此，在这一个方法下，S集合内的每个元素都可以被表示为一对A、B集合内的元素。

结论7：

证明：

从黑圆点运算的定义可以知道(20)中的第一个等号是成立的（那两条公理），由于引理6可知，a 白圆点 b的结果就是x（A 白圆点 B = {x}, a∈A, b∈B）。又由于定义的半中心双群的幂等性，因此有：a 白圆点 a = a ∈ S，所以有：a 黑圆点 x ∈ S 黑圆点 x。后面的推理类似，从而得出其结论。

这里的结论揭示的是，对于S集合内的任意一个元素x，都可以通过定义引理6中的两个集合A,B，然后通过对两个集合中的元素做对应半中心双群中的运算来表示x。并且，解释了以各种对于结果相等的两个运算之间的运算右侧元素可以相互替换原则（这个性质 very very very important!）。

于是，作者对满足这一特性的元素对，做了一个集合，并用一个符号进行表示。

这一个集合是一个partition，且其结构是这样的：

那么，对于这个集合内的元素，在引理6下，可以得到其一个性质，就是：

作者又引入了一个新的性质

这里一个重要的区别就是，R2跟Q1中一个是y一个是x，因此没有Q1∩R2={x}，而是需要做一个变换。具体的解释如下：

定义7：

【我已经快死了，这TM才到了8/33，真的要命，这论文读的...理论计算机科学，真的杀人】

定义7就是很直白的定义，说明了这个有序对集合的一些性质，且在存在的矩形与基集合之间又可逆映射时是幂等的。

然后作者举了一个简单的有序对集合的例子。

例子：

这里的例子，重点就是理解下面的描述。(s,t)是A^2集合内的一个元素，那么在{s}×A这个长方形里也是唯一的，因为再A中t这个元素只有一个。从关于R的定义中可以看到，R=(R1,R2)=R1×R2，因此给定R={r}×A，得到R1={r}，同理Q=(Q1,Q2)=Q1×Q2，Q={q}×A，则Q2=A所以|R1∩Q2|={r}。

下面作者给出了更一般的rectanglar structure的形式。

理解：

作者将上面提到的半中心双群和矩形结构联系起来，提供了二者之间的映射关系。

推论8：

推论8给出了矩形结构内数量性质。原文给出了证明，所有证明都是证明这些映射之间是双射，从而证明其数量相等。下面直接给原文。

证明：

（这块证明，看的有点绕，感觉理解又不太理解...）

作者通过这个证明，告诉我们，集合S可以作为原像，通过集合S可以定义的矩形结构是Dagwoods。

3.2 Deriving an algebra

黑圆心运算，做的是一个S×S映射到S的运算，下面就是举例：(s,t)是S×S上的一个元素，u是S上的一个元素。由于矩形结构和半中心双射的对应关系可知，u还等于后面的式子。

白圆心运算，做的是一个S×S映射到S的运算，也可以做类似的运算。

俩运算过程如下：

推论9：

推论9指的是上述定义的代数是幂等的半中心双群。

证明：

证明的解释：

将(35)、(36)定义的运算带入，可以得出运算结果。

从这一个vanilla rectangular structure的例子中，代数(S,黑圆心)与(S,白圆心)都是矩形半群。

结论8：

证明：

结论9：

这里的证明，利用到了推论8的内容。

结论10：

这里用到了结论9的内容，如果对于第一个黑圆点运算有形式(a,b)，那么第二个黑圆点运算就有形式(b,a)，但是黑圆点运算时一致的，因此两个形式时一致的，因此a=b，所以有|S|=ab=a^2。

4. Reversibility of cellular automata

细胞自动机以及可逆细胞自动机的定义：

引理11：

如果一个细胞自动机可逆，那么它的逆也是细胞自动机。这是显然的。

将h定义为一个对细胞自动机的映射运算，其就是将长度为2r的细胞自动机的状态集合S=A^2r 的平方映射到一个S上。可以得到集合S与运算h可以成为一个群。

这段就是说明了可逆的细胞自动机刚好可以表示为一个半中心双群，因此半中心双群的方法可以很好的应用于研究可逆的细胞自动机。

5. Graph model

这一个部分，主要介绍了图对于半中心双群（一般的，不一定非得幂等）的一种等价模拟关系，这中对应关系在中心群内也有体现。

5.1. Digraphs（有向图）

在图论中，有一个由有向图所决定的问题是这样的，每一对节点都是被一个单一的给定长度的路径所连接的。这也被成为UUP_n。当n=1时，可以得到一个简单完全图且对于更长的路径的情况，可以发现更多的结果类。

inter-prosessor communication 图提出了一个问题。一个合适的解释是，作者提出了一个双色边的有向图，双色分别是红与蓝，对于每一对节点(a,b)之间，存在一条直接的长度为2的红-蓝路径，每个红边都跟这一个蓝边，且假设所有节点有一个任意颜色的回环。我们将这个称之为unique 2-coloured 2-path graphs。

后面讨论接下来的迭代。设一个关于绩点的固定集合，从这个集合里着眼两个方向的图，一个是G_R，另一个是G_B，并各自称之为红图与蓝图。问题是如何安排这些图使得当我们将他们重叠在一起的时候，任意两个点之间，都有一条唯一的长度为2的双色（blue-red）路径，和唯一的（red-blue）双色路径。我们可能需要假设所有节点的每种颜色的路径都构成循环，但这是没必要的。我们必须允许同一节点对中存在两个不同颜色的不同边。因此，我们应该讨论多重图，因此多重图类可以被称为symmetric 2-coloured unique 2-path multigraphs。

图1 是将每个节点的回环删除之后的一对双色路径图的示例。

这些例子的一个广义类可以被简单的构建为方格（grid），将任意一个Z×Z中的一个矩形视作一个点集合，将所有的点用红边连接到一条平行线上，然后将所有的点也在一条垂直边上用蓝色的弧线连接。则为了得到沿着红蓝通路的从某个点到另一个点，首先从水平线上沿着红边到达对应的垂直线，然后沿着蓝边到达对应的点，类似于曼哈顿街道图。如果要找蓝红边则是将顺序颠倒。

注意到这些图的incidence matrices（关联矩阵）有这样的性质：AB=BA=J，其中A,B是关联矩阵，J是一个有1组成的矩阵。正如由Hoff'man提出和由Knuth研究的矩阵，对于0-1矩阵A如果有A^2=J是已经被证明的。对于0-1矩阵A，是否有A^n=dI+入J，仍是一个有趣的问题。

5.2 Connections

在这一部分，作者将证明有循环边的有向图与幂等的代数结构是等价的。

构造12：

这个说的是，如果a点能通过一条红（蓝）边到达b点，那么可以认为存在一个c点，使得a通过与c点一个黑（白）圆点运算得到b点，这就跟群联系上了；然后通过加入一个中间点c，可以得到从a点通过红（蓝）边到c_r（c_b）点，然后再通过一条蓝（红）边到达b点，则定义a跟b的黑（白）圆点运算可以得到对应的c点，这就是一个代数结构了。

推论10：

如果一个代数结构是半中心双群，那么上述的结构可以定义一个对称的双色唯一双路径多图。相似的，给定一个对称双色唯一双路径多图，上述结构也可以定义一个半中心双群，这个结构是可逆的。

对于推论10的证明是比较显然的。

如果节点a是幂等的，所以有a黑圆点a=a，则有a节点有一个红回环边，同理蓝回环边也是一样的。因此，如果S是幂等的，每一个节点都有一个回环边，如上述的案例。

那么，假定两个类，S是一个半中心双群，G是一个对称的双色唯一双路径多图。如果从S与G中的函子由上述构造12描述，取S中的一个序列A->f B->g C。因为f，g两个映射运算的是两个半中心双群中的元素，他们在函子下的图节点中的运算，也可以携带边。因此在图G中range(f) = ker(g)，所以函子也是确定的（这一段是直译，我的理解，可以结合上面定义的结构来理解，将f看成黑圆点运算，g看成是白圆点运算）。那么我们得到如下结果：

引理13：

引理13说的是同构的半中心双群可以根据构造12给出一个同构的图对。

因此，在图对和半中心双群是等价的，如下内容可以说明一个半中心双群的自同构的群可以由一个相互连接的图的自同构群来得到，这在组合数学中已经得到充分研究。【所以，作者默认读这篇论文的人都了解组合数学吗？？？晕~】

引理14：

这里说的是，如果G_b与G_r是由半中心双群S定义的，那么有S的自同构等于G_b的自同构交G_r的自同构。

证明如下：

因此，可以使用为确定图的自同构而开发的算法来轻松确定半中心双群的自同构群。这是一个特殊的问题，与后面关于半中心双群提升的独特性的结果有关，而且它在构造我们将在第8节中研究的矩形结构的例子中也具有相当大的价值。尽管可能有直接确定幂等半中心双群的自同构群的技术，但超越为确定图自同构而开发的高效算法所需的工作量可能相当高。

6. Uniqueness of semicentral bigroupoids

在本节中，我们研究了同构的概念和确定半中心双群之间同构的方法。这可以扩展到一种计数方法，这样给定给定大小的幂等半中心双群的详尽列表，我们可以精确地计算存在多少个该顺序的半中心双群。二元性和对称性再次使我们的工作更轻松。

引理15：

引理15说的就是，如果某个映射对于两个半中心双群中，如果对于其对应的某个运算对应的群是同构映射，那么对于另一个运算也是同构映射。证明还是比较清晰的，就是直接代入运算。

通过这个引理，我们可以看到任何一个半中心双群都是一个幂等的半中心双群的“lifting”。此外还有：

引理16：

引理16指的是每一个半中心双群都与一个矩形结构相联系且在"lifting"中都是固定过程。

推论11：

推论11说明了，两个半中心双群的同构性与其相联系的矩形结构的同构性一致。

充分性的证明方式就是给定两个同构的半中心双群，然后分别对其对应的矩形结构进行同构运算，如果可以通过一个矩形结构可以用这一个同构运算得到另一个；然后通过该同构运算的逆运算，再做一次运算，如果可以推出原来的矩阵结构，则证明完毕。

必要性的证明则是证明同构映射可以保持关联的矩形结构，如上。

推论11告诉我们，一个给定一类非同构的矩形结构，我们是无法得到同构的幂等半中心双群的，反之亦然。矩形结构跟幂等的半中心双群是完全等价的。

上述的图论没有提及幂等的条件，因此作者在后续考察了非幂等半中心双群有啥性质。

推论12：

推论12介绍了，两个同构的半中心双群，其同构映射已知。当且仅当他们的幂等"lifting"与同构映射是同构的，且其各自的平方映射满足上述等式。

证明：

充分性，通过已知的幂等"lifting"计算和给定的同构映射代入做运算，最后得出等式取逆即可证明；必要性，对两个半中心双群中的一个，代入一个幂等"lifting"的运算及其逆运算和做同构映射，进而可以计算出同构映射与幂等"lifting"的结合可以得到另一个半中心双群的同构映射与幂等"lifting"，然后幂等"lifting"的逆运算与后面的式子结合得到证明开头定义的式子。通过将同构映射代入的操作，得到（89）式子，进而从新运用开头定义的式子，得到（90）式子，然后刚好出现一个幂等"lifting"及其逆运算，可以消去，得到最终结果。证毕。

紧接着，作者开始提到Symm(S)这个S上的对称组的性质，Symm_RS(S)是矩形结构(S,黑圆点,白圆点)这个半中心双群上矩形结构的一个对称组，定义[a,b]=aba_(-1)b_(-1)是Symm(S)中关于a,b的置换(permutation)。

引理17：

引理17给出了半中心双群的同构"lifting"的充分必要条件。

证明

推论13：

推论13说明，幂等半中心双群的两个"lifting"是同构的，当且仅当两个"lifting"是由Symm_RS(S)中的一个元素共轭的。

证明：

为了将一些特定规模的半中心双群进行分类，仅需要决定该规模的矩形结构，找出其对称组，取其在Symm_RS(S)的Symm(S)中的共轭类。

7. Counting semicentral bigroupoids

在这一小节，作者举例说明了如何数出一个给定的幂等半中心双群的非同构"lifting"的数量。

给定一个矩形结构R，可以找到它的对称组 G = Symm(R) < Symm(S)。这一性质可以通过引理14中的图模型找出幂等半中心双群的自同构群。这些Symm(S)上的自同构行为是共轭的。从前面的内容中，每个与一个在矩形结构R上的半中心双群"lifting"的一个同构类与一个orbit相对应。因此，问题变为了如果数出orbit的数量。

作者将这一个问题构建成就组置换的问题。让G:=S_n 对于一些n，并且去一些子组K<=G。则使得G由在K下同构的orbit的数量，可以通过Burnside的引理得到：

其中，t是orbit的数量，F_G(k)是由k所固定的G的元素的集合。但这仅仅只是G中的k的一个中心化。

如果我们着眼于G与其自身的共轭操作，通过数出子群C_G(k)的合集，可以得到：

Gk是在G下的k的orbit的共轭。

可以知道Gk是与k共轭的所有G元素的集合，且这个集合与k有着相同的圆圈结构。如果k有一个长度为a_i的t_i圆圈的圆结构，包括长度为1的圆，那么有：

引理18：

证明：

由于G的数量关系与引理18可知：

通过计算每一个k属于K的元素的|C_G(k)|之和，可以得到orbit的数量如下：

推论14：

这个结论给出了同构的非唯一性。给定一个矩形结构或者相对的幂等半中心双群，可以轻易的计算其对称组，并决定其非同构"lifting"对的数量。

8. Generationg rectangular structures

作者研究了使用增量过程全面构建具有给定格式的所有示例的方法。这些方法利用内部对称性和其他结构来显着减少搜索空间，并避免或删除同构示例。所研究的方法是两阶段方法，生成然后删除同构副本。然后，我们看看另一种方法，该方法通过跟踪生成树中可能的分支来仅生成非同构示例。我们比较这两种算法，看看哪个更古老。所有技术都使用分支生成树来逐个生成示例。trade-o介于增加生成树算法的复杂性和增加努力以删除生成的列表中的同构副本之间。

在这个小节，作者提出了各种伪代码算法。

8.1 Partial rectangular structures

这一部分，作者提出了穷举所有特性形式矩形结构的方法。这个方法是通过从更简单的非完全样例中构建出样例，在分支处理中，每个不完全样例可以被许多不同的方式构建出来。这些方法被提出去通过仅仅使用规范的外延，正向的一部晚宴和一场同构外延，来减少非必要的分支。然后，我们研究对列表进行排序的技术，筛选出重复项。此处的定义也与其他技术相关。

定义15-17：

可以看到一个矩形结构是一个部分矩形结构。部分矩形结构可以通过公式（25）的覆盖要求来生成矩形结构。一个全部分矩形结构拥有nm个矩形。这是一个矩形结构。

样例：

我们可以得到一个带有两个矩形的部分矩形结构。这个矩形还可以是上述序列的一个最小的矩形，且可以加到其他前面的矩形。

我们可以通过字典排序来排列矩形来排序同样规模的部分矩形结构。这在一个代数的计算机语言如GAP中应用算法是是否有用的，其中集合被定义成无重复的有序列表。算法预先定义的结构集合也因此在系统上没有额外的负担。

将S_nm这一个在{1,...,nm}上的对称组，自然的作用部分矩形结构。

定义18：

定义19：

8.2 Algorithems

自此，我们可以得到一个自然算法。假设一个函数pos_noe_ext(P)，给定一个部分矩形结构P，可以返回所有可以加上P形成一个正向单步外延的矩形的集合。通过深度有心啊分支树聚集最小部分矩形结构(112)的所有扩展的完整列表，然后再S_mn下取orbit并且在每个orbit中选择最小的满部分矩形结构，就会形成一个简单但是效率比较低的算法。

一个更加有效率的办法必须要检查当前部分矩形结构中同构的方面并且仅仅拓展其中代表性的一个，试图避免多条导向同一个矩形结构的通路。

作者仅仅需要考虑一些对于部分矩形结构的外延，因为他们仅需要具有代表性的满菊粉矩形结构和有代表性的矩形结构。

推论20：

任何一个代表性的部分矩形结构是一个代表性的部分矩形结构的正向单步外延。

证明：

【时隔许久的吐槽，从第五节开始，这个作者就在疯狂甩设定，然后疯狂自己的设定之间存在等价关系；然后，每个概念都是提出来但是不好好说明，阅读难度骤增...】

注意到，这部是意味着代表性的单步正向外延是必要的，或者部分矩形结构P的单步正向外延总是P的代表。这个允许我们去缩减许多搜索树的分支，因为任何一个部分蛛形结构如果不是代表性的则不可能是我们的目标，并且也没有必要去延展它。

然后，作者根据这个提出了他的算法：

算法：

【这个伪代码比较简单，但是其中有一些操作还是需要理解一下，如：Aut(P)，以及怎么取G下的S的Orbit，还有find_all_rs(Union(P,{rep}))是啥意思，需要跟上面的论述内容结合才能理解...】

作者让所有的候选项都便利知道他们成为矩形结构而不是使用额外的对非完全部分矩形结构的额外测试，然后通过测试样例之间的同构性来拒绝同构项，这一个技术会在下一个部分介绍。相似的证明表明，图、部分代数和部分矩形结构自同构都是等价的。

定义21：

引理19：

证明：

定理22：

证明：

这一段直接就放原文了，证明分了三个部分，第一个是部分矩形结构P只有一个元素时，直接成立，然后当P有k+1个时，可以从推论20中得到其代表性的P’，因此可以被算法找到。

因此，这个算法的结果列表时完全的。后续的部分分为筛选列表中同构的。然后找一个可以进一步减少生成样本的数量的技术。

8.3 Sieving the full partial rectangular structures

上述算法已经可以找到一大批矩形结构，但是即便该算法已经极大的缩减了分支，但是仍然无法了解是否有所有成对的非同构，如果这些例子时代表性的。传统的办法会导致难以克服的空间复杂度，因此需要一个更有效率的办法。

由于矩形结构与图对（带循环）是等价的因此，两个矩形结构之间的同构问题等价于两个带循环的图对之间是否痛殴。图的所有节点都有循环边，因此在决定同构性的时候可以忽略。图同构在图理论上是一个成熟的问题，可以有一个有效率的算法计算图同构。

算法伪代码如下：

这个算法也是比较直接的，直接口语化的表述，因此直接原文。其中需要理解的就是看看怎么从矩形RS里计算graphpair。

作者还提到，尽管这个办法已经简化了很多复杂度，但是仍可以通过组合的性质来进一步简化，因为这可以避免判断图的同构性。可以将两个图结合成一个图，两个图对的同构性与两个结合图的同构性是等价的。如果(A,B)在点集合{1,...,n}上的图对，那么利用标签a和b可以凑早一个新的图，节点和边如下：

可以看到，从两个图对构造的图是同构的当且仅当两个图对是同构的。

8.4 Prohibited extension

【读到这里，人已经麻了~读后忘了前面，加上最近事情实在是多...断断续续在读，快扛不住了，都是一些新概念，T_T】

算法find_allrs生成了许多非代表的样例，接下来的结果让我们能够避免许多已知被其他地方生成的外延。

推论23：

推论23说的就是一个代表性的部分矩形结构P，如果存在一个矩形R使得其与P的并不是代表的，但是存在一个映射关系可以是其成为代表的，那么存在一个j可以使得P‘的映射关系运算之后还得到其本身，映射关系属于P’的共轭，且P'并映射R是一个P‘的正向单步外延映射R<R_(j+1)。

为了使用这个结果，作者递归地传递部分矩形结构，并带有收集prohibited的扩展。如果R<T是矩形且是最小的一个部分矩形结构P的正向单步外延，那么Aut(P)(R)是被加入P∪{T}的prohibited集合。

这要求计算Aut(P)(R)时没有额外的时间花销。而且，减少分支在也会减少筛选同构样例的时间花销。

8.5 Orderly algorithms

一个保障分支生成不会生成同构样例的可选办法，因此删除算法的筛选步骤。通过仔细地bookkeeping，这是可以实现的。这些生成步骤已经被成为"orderly"。

这个部分介绍了Royle的办法，然后描述了算法的必要功能。我们那么找组合的特质取加速算法。

设V是一个集合，G=Aut(V)。我们将在v∈V上的g∈G的行为和自然而然的延拓到集合上的行为写为v^g。作者想要找到所有的子集X包含于V使得P(X)对于一些P的遗传性质是真的，但是他们只想要一个从每个同构类中的一个样例，同构性被定义为G。

我们需要一个函数Θ使得：

Θ: 2^V -> 2^V，

Θ(X)是G_X在X上的一个orbit，

对于任意的g∈G，都有Θ(X^g)=Θ(X)^g;

G_X是X的一个稳定，G_X={g∈G|X^g=X}。

让T_k是规模为k的集合个一个集合，使得P(X)对于所有的X都有X∈T_k，且T_k不包含任何同构。作者提出了从T_k中产生T_(k+1)集合的一个算法：

算法伪代码：

这个代码，最关键的就是理清各个符号的意思，算法本身不难。

定理24：

定理24说，如果T_k只包含一个V的k-集合的G-orbit的代表且拥有P的性质。那么有算法产生的T_(k+1)集合也是只包含一个V的k+1-集合的G-orbit的代表且拥有P的性质。

从T_0={⌀}开始，用一个orderly算法取构建一个带有P性质的V的子集的一个代表。这就是我们定义的函数Θ。

定义25：

这意味着如果我们在图的自同构组下取最小的规范化标签指向图的orbit，那么无论我们怎么重新标记这个图这个orbit都是唯一确定的。这也是形成了我们定义Θ的一个机制。

我们的状况是这样的，集合V是一个n×m的矩阵的集合，P是成为一个部分矩形结构的性质。我们想要找出全部分矩形结构的集合T_nm，也是矩形结构。

让花体R是一个部分矩形结构，R∈花体R是被考虑的外延。Θ必须从花体R上的G_R中选择一个orbit，想要了解R∈Θ(花体R)是否成立。首先通过组合值来进行选择。一个组合值v:V×2^V->Z是一个G的orbit上的常数，v(x,X)=v(x^g,X^g)对所有的g∈G都成立。下面的组合值将会被使用：

让v=v(v_1(R,花体R),v_2(R,花体R))。如果v是在所有R∈花体R中的一个唯一的最小值，那么R∈Θ(花体R)且我们通过R和递归获得所有的外延。如果v是最小的但是不唯一，那么我们用规范化标签从花体R的图中的集合{dQ:Q∈R}上选择最小的标签元素m，且让Θ(花体R)=m^(G_R)。如果R是在这个orbit中的，我们就递归，否则我们就不继续这个外延。

8.6 Results

【只能说Finally，读到这里，我人都晕了~全是概念，群、半中心双群、orbit、图、矩形结构、部分矩形结构、全部分矩形结构、矩形...】

时间对比这部分就不介绍了~可以自己看论文...放上对细胞自动机的结果

关于结果表格，B站最多上传100张图片，因此我没放，可以自己到论文里看...

其中：

Size列表示的是状态数量，Idempotents列是所有静止状态规则的数量，Lifting列是非重复规则的总数。只有一个平凡细胞自动机规则(保持和左右移动，带"lifting")，形式是1×x和x×1，所以这些被忽略了。作者还忽略了很多其他情况，可以看原文去了解。

9.conclusion

还说啥呢？就是提出了一个新办法，然后论证了这个办法的有效性，提出了可以应用这个方法的普通算法，然后通过引入多个领域的理论，优化了这个算法。

【文末】

吐槽：

读完这个论文，感觉就是这个论文阅读难度还是挺高的，如果对于一些代数学上的概念不太清楚，真的会看不懂，然后作者还自己定义了许多内容，每个内容之间的引用都不是紧接着的，而是兴致到了就告诉我这个结论是基于前面提到的某个内容，这时就需要你不断翻页去看这个，然后思考怎么把这个应用到这里。然后作者的证明，基本上都是一些代入计算，如果对某些他自己定义的东西或者运算的理念不了解，根本证明不下去~虽然作者用了细胞自动机做题目，但是通篇内容，都没有太使用细胞自动机的语言，而是完全通过代数相关的内容来行文，因此即便是细胞自动机相关领域的人来看这个论文，也没有多少熟悉度。有时候，看着这个论文，连翻译都很困难，因为很多都是数学名词，实在是不熟悉。这篇论文就是属于曲高和寡的那一类文章...

作者提出的伪代码，根本就是纯口语表达，计算细节是一点都不提供，不过提到了一些语言包的实现方法...我没有特别去提。

我的感受就是作者写的比较碎，属于我需要哪个概念了，就提出来，然后进行论证，论证之后我就在后面某个地方引用，但是引用方式基本都是告诉你这俩概念是等价的，可以通过某个运算方式转化的。

深刻感受到了B站对转栏对这类稿件编辑的不便，根本不提供公式内容的编辑渠道（也可能是我不太会用），后续内容可能会转移到知乎啥的，当然如果有视频稿件会及时进行更新...

心得：

本文作者通过首先定义了半中心双群，然后提出幂等的半中心双群，然后通过证明矩形结构跟图对(红蓝双路径)与幂等半中心双群的等价性，以及可逆细胞自动机与幂等半中心双群的等价性，将细胞自动机问题转化成代数结构上的问题。

然后继续引入新的概念，部分矩形结构，以及全部分矩形结构，然后通过同构映射将这些内容联系起来，把问题又变成了找图上的同构对啥的，进一步简化了问题。

在结果上，作者尝试了多状态的细胞自动机，并且号称穷尽了可逆一维细胞自动机。