目前參與的科研項目，需要閱讀的論文難度都有點大，所以開個小坑來記錄一下閱讀筆記，免得以后忘了還得重新讀。當然，因為這些內(nèi)容都是跟代數(shù)強相關(guān)的，因此我作為一個文科背景的跨專業(yè)人員，可能會有很多理解上的失誤，有高手看到了，還望不吝指出并及時賜教...、

話不多說，開坑?。。?！

論文題目：Efficient exhaustive listings of reversible one dimensional cellular automata

論文作者：Tim Boykett

摘要

本文關(guān)注一維細胞自動機的一個代數(shù)構(gòu)造。使用的構(gòu)造方法與組合結(jié)構(gòu)和圖論的聯(lián)系變得清晰。關(guān)于唯一性和同構(gòu)性的有力結(jié)果使我們能夠概述用于生成可逆一維元胞自動機的詳盡列表的有效算法，并計算存在的不同示例的數(shù)量。這些算法使用“有序算法”方法來避免暴力搜索的陷阱。

1.引言

沒啥硬核內(nèi)容。

第一段。介紹了作者自己方法的優(yōu)勢，點出了細胞自動機研究中存在的語言不不統(tǒng)一問題。本文通過擯棄原有的細胞自動機語言體系，是的本文可以通過已有的代數(shù)、組合結(jié)構(gòu)和圖論的工具對細胞自動機的性質(zhì)進行研究。

第二段。重點介紹了可逆性計算的含義，就是能夠讓細胞從最終狀態(tài)回復到最初狀態(tài)。關(guān)注可逆性計算的好處是，可以將重要的額外結(jié)構(gòu)包含進去（我猜測這里的意思是可以讓細胞自動機包含更多的信息）。這與半群（可轉(zhuǎn)換的）和群（轉(zhuǎn)換時不可逆的）的不同是相當?shù)摹具@句我理解起來可能會出錯，所以直接給原文，原文是：This is comparable to the differences between semigroups (of transformations) and groups (where the transformations are invertible).】。這個額外的結(jié)構(gòu)可以讓人們從那些可能不可逆的樣例中找出更多的對象（猜測可能是可逆對象）。并且，已有證明論證，這中可逆性對計算能力也沒有任何的限制。

第三段。介紹文章結(jié)構(gòu)，先從代數(shù)的某些概念出發(fā)，并提出了一些重要的性質(zhì)。如：廣義半中心雙群（general semicentral bigoupoids）可以被表示為一個冪等的帶有相關(guān)排列的半中心雙群（semicentral bigoupoid），稱為“l(fā)ifting”。然后，我們協(xié)調(diào)代數(shù)結(jié)構(gòu)并導出一個組合對象，一個矩形結(jié)構(gòu)。以下各節(jié)顯示組合對象是直接的等效于冪等半中心雙群胚。

第四段。作者提到他們利用Pedersen的技術(shù)證明了冪等半中心雙群等價于一個可逆的細胞自動機。

第五段。作者提到他們引入了代數(shù)和組合結(jié)構(gòu)作為一對圖的進一步模型，并證明它是等價的。重要的是，代數(shù)結(jié)構(gòu)和圖結(jié)構(gòu)的自同構(gòu)群被證明是相同的。然后，我們研究半中心雙群之間的同構(gòu)，準確確定兩個半中心雙群何時同構(gòu)，并開發(fā)一種技術(shù)來計算可以從給定的冪等半中心雙群中提升的不同半中心雙群的數(shù)量。然后我們找到一種逐個構(gòu)建半中心雙群體的技術(shù)，表明我們可以使用這種技術(shù)生成所有示例。作者提到他們應用一種用于窮舉生成矩形結(jié)構(gòu)的電子算法。使用同構(gòu)結(jié)果，我們可以計算不同的半中心雙群的數(shù)量，從而計算可以導出的元胞自動機規(guī)則從那個結(jié)構(gòu)。

【這個引言，基本上是翻譯，第五段就是說作者做了那些努力來找出合適的算法】

2.代數(shù)結(jié)構(gòu)

作者在這個部分介紹了什么是中心群和半中心雙群

2.1 定義和簡單的結(jié)果

群（goupoid）的定義：(2)-algebra (S, ·)，其中?·運算時二元運算，如下圖：

雙群（bigroupoid）定義：當然運算也都是二元運算

群的一些性質(zhì)：

引理1：

這三條性質(zhì)中，第一條說明的是某些集合的笛卡爾積滿足與*號運算與群等價；第二條說明如果二元運算的左右兩端可以交換位置等價于左右兩端元素相等；第三條則是群也是一個具有a·b·a=a的冪等半群。

定理2：

該定理說明一個有限的中心群中的元素個數(shù)一定是某個整數(shù)的平方階。每個正整數(shù)都存在一個其平方階的中心群。任何整數(shù)平方階的中心群，其冪等數(shù)就是該整數(shù)。對于大于等于3的整數(shù)有其平方階的非天然中心群。

Knuth探索了中心群的多個方面，并且發(fā)現(xiàn)了兩個中心群的模型，一個是圖模型，另一個是基于 {0,1}-矩陣的模型，這些矩陣是這些有向圖的入射矩陣（incidence matrices），這些{0,1}-矩陣A由如下性質(zhì)：A^2 = J, J矩陣完全由1組成。

作者還提出，窮盡所有的中心群與窮盡所有的矩陣符合如上性質(zhì)是等價的。

定義3：

一個半中心雙群滿足如下公理：

還有如下性質(zhì)：

此處，說明了如何通過一個中心群產(chǎn)生一個半中心雙群。且半中心雙群的運算符號是對稱的，因此只需要關(guān)注其中的一個。通過對運算進行簡單的的定義，可以定義一個左保持半中心雙群，或者右保持半中心雙群。這兩種雙群都是平凡的?！疚矣X得這里可以對應細胞自動機中的平凡規(guī)則】。

例2：

從例子中可以看到，定義的半中心雙群Q是集合A和B的笛卡爾積，且定義的運算是封閉的。黑圓點運算，得到的結(jié)果是左元素對的左元素和右元素對的右元素組成的新元素對，這個元素對也是集合Q內(nèi)的某個元素。白圓點運算的分析類似，且結(jié)果也在集合Q內(nèi)。

接下來驗證是否滿足兩條公理：

證明過程比較簡單，而且隱含了冪等性。

這個樣例與自然的中心群相對應，且可以被構(gòu)造為“點乘”。此處的（Q,黑圓點）和（Q,白圓點）都定義了一個長方形的半群。如果一個半群是關(guān)聯(lián)的（associative），其對應的半中心雙群也是。而且，所有的關(guān)聯(lián)半中心雙群都與樣例的形式一致。

引理3：

引理3說明了半中心雙群的兩個計算是反交換的（反交換性條件比無交換性更強），當且僅當運算兩端的元素相等時，才能夠做等價交換；且由此可以推出兩個運算都符合冪等性，這塊在樣例的證明里已經(jīng)體現(xiàn)。

簡單證明：

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，不知道怎么定義這個逆運算，也可能是我自己多想了，總之，在推理上是沒問題的?！?/p>

2.2. Lifting

從任意一個半中心雙群做“折疊”可以得到另一個半中心雙群。這是找尋半中心雙群新樣本的一個方法。

命題4：

如果存在一個半中心雙群，以及一個關(guān)于對應集合的置換【這里的permutation，還有排列的意思，如果翻譯成這個，我感覺有點對不上】，可以通過將新的運算與原運算和置換做一個對應，得到的新的代數(shù)也是一個半中心雙群。

作者還提示，一般而言，新的半中心雙群與原來的半中心雙群不是同構(gòu)的。

【TNND，又有一個新詞匯isomorphic，同構(gòu)。對一個跨行的人而言太TM不友好了，同構(gòu)的定義（維基百科）：

我的理解就是從A->B可行，那么從B->A也可行，且A內(nèi)元素跟B內(nèi)元素都是一一對應的?！?/p>

定義5：

【開始難起來了，代數(shù)要求開始變高了...TNND】

這里定義了“l(fā)ifting"操作，就是將一個原有的半中心雙群通過一個運算（上文提到的置換，permutation），得到一個新的半中心雙群。這里提出了一個運算：平方映射，和這個平方映射的逆運算：逆平方映射。

從命題4中給出的新半中心雙群中所定義的新運算看，這個平方映射恰好可以和前面的逆平方映射計算得出原有的元素，因此得到一個新運算時冪等的。而且，如果對一個被平方映射lifting所的到的半中心雙群做一個基于逆平方映射的lifting，則可以得到原來的半中心雙群。

【這不就是一個雙射嗎？所以這不是一般情況...】

作者在這里得出結(jié)論，這種lifting的操作時可逆的，且每一個半中心雙群都是一個冪等的半中心雙群的lifting，且其permutation（置換？排列？）都能變?yōu)槠椒接成涞哪妗?/p>

并且，作者提到在半中心雙群中可以有任意的permutation作為平方映射并且任意數(shù)量的冪等，與中心群的冪等不同，中心群的冪等要求等于有限集合內(nèi)元素數(shù)量的開方。

此處，作者定義了一個新的符號Symm(S)來表示集合S是對稱群。

推論6：

作者這里提出，每個半中心雙群都可以被唯一的表示成一個冪等的半中心雙群和其對稱集合上的一個permutation。相反的，當僅當permutation時平凡的時，才能給出這些冪等的半中心雙群對。

將冪等lifting的過程應用到中心群中，獲得一個半中心雙群。定義好相關(guān)集合和運算后，可以的到下列表格：

為了更好的說明，這里用手推一下，過程如下：

引理4：

這里說的就是一個自然中心群在冪等lifting后得到的半中心雙群是關(guān)聯(lián)的。

2.3 關(guān)聯(lián)的半中心雙群

上述的等式(13)的詳細推理，應該是這樣：

從而得到了

引理5：

【到這個地方，section2算是搞完了，整體來說這倆部分還是不太難的。但是，篇幅才到了6/33，我真的TM了】

3.矩形結(jié)構(gòu)

這一個部分舉例說明了所有的半中心雙群都等價于一個確定的組合結(jié)構(gòu)。通過這樣的等價，作者確定了這些代數(shù)結(jié)構(gòu)的一些性質(zhì)。這部分提及的所有半中心雙群都是冪等的。

3.1. Partition

【這個名詞，實在不知道咋翻譯，翻譯成分區(qū)也太抽象了...T_T，我覺得這里的意思跟離散數(shù)學里的那個partition差不多。】

【開始抽象起來了，md！】

這里實在是，一時半會想不清楚想表達的意思。我的理解是：這個先對S集合做平方，然后再通過P(S^2)這個定義一個S^2的冪集。下面則是這個集合里每個元素的定義。

引理6：

推論6就是給出了半中心雙群和定義的組合結(jié)構(gòu)之間的聯(lián)系。

對于推論6的證明：

引理6定義了一個運算，可以將S^2這個集合分割成標準乘法的集合，且是可以由rectangles組成的partition。因此，在這一個方法下，S集合內(nèi)的每個元素都可以被表示為一對A、B集合內(nèi)的元素。

結(jié)論7：

證明：

從黑圓點運算的定義可以知道(20)中的第一個等號是成立的（那兩條公理），由于引理6可知，a 白圓點?b的結(jié)果就是x（A 白圓點 B = {x}, a∈A, b∈B）。又由于定義的半中心雙群的冪等性，因此有：a 白圓點 a = a ∈ S，所以有：a 黑圓點 x ∈ S 黑圓點 x。后面的推理類似，從而得出其結(jié)論。

這里的結(jié)論揭示的是，對于S集合內(nèi)的任意一個元素x，都可以通過定義引理6中的兩個集合A,B，然后通過對兩個集合中的元素做對應半中心雙群中的運算來表示x。并且，解釋了以各種對于結(jié)果相等的兩個運算之間的運算右側(cè)元素可以相互替換原則（這個性質(zhì) very very very important!）。

于是，作者對滿足這一特性的元素對，做了一個集合，并用一個符號進行表示。

這一個集合是一個partition，且其結(jié)構(gòu)是這樣的：

那么，對于這個集合內(nèi)的元素，在引理6下，可以得到其一個性質(zhì)，就是：

作者又引入了一個新的性質(zhì)

這里一個重要的區(qū)別就是，R2跟Q1中一個是y一個是x，因此沒有Q1∩R2={x}，而是需要做一個變換。具體的解釋如下：

定義7：

【我已經(jīng)快死了，這TM才到了8/33，真的要命，這論文讀的...理論計算機科學，真的殺人】

定義7就是很直白的定義，說明了這個有序?qū)系囊恍┬再|(zhì)，且在存在的矩形與基集合之間又可逆映射時是冪等的。

然后作者舉了一個簡單的有序?qū)系睦印?/p>

例子：

這里的例子，重點就是理解下面的描述。(s,t)是A^2集合內(nèi)的一個元素，那么在{s}×A這個長方形里也是唯一的，因為再A中t這個元素只有一個。從關(guān)于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的形式。

理解：

作者將上面提到的半中心雙群和矩形結(jié)構(gòu)聯(lián)系起來，提供了二者之間的映射關(guān)系。

推論8：

推論8給出了矩形結(jié)構(gòu)內(nèi)數(shù)量性質(zhì)。原文給出了證明，所有證明都是證明這些映射之間是雙射，從而證明其數(shù)量相等。下面直接給原文。

證明：

（這塊證明，看的有點繞，感覺理解又不太理解...）

作者通過這個證明，告訴我們，集合S可以作為原像，通過集合S可以定義的矩形結(jié)構(gòu)是Dagwoods。

3.2 Deriving an algebra

黑圓心運算，做的是一個S×S映射到S的運算，下面就是舉例：(s,t)是S×S上的一個元素，u是S上的一個元素。由于矩形結(jié)構(gòu)和半中心雙射的對應關(guān)系可知，u還等于后面的式子。

白圓心運算，做的是一個S×S映射到S的運算，也可以做類似的運算。

倆運算過程如下：

推論9：

推論9指的是上述定義的代數(shù)是冪等的半中心雙群。

證明：

證明的解釋：

將(35)、(36)定義的運算帶入，可以得出運算結(jié)果。

從這一個vanilla rectangular structure的例子中，代數(shù)(S,黑圓心)與(S,白圓心)都是矩形半群。

結(jié)論8：

證明：

結(jié)論9：

這里的證明，利用到了推論8的內(nèi)容。

結(jié)論10：

這里用到了結(jié)論9的內(nèi)容，如果對于第一個黑圓點運算有形式(a,b)，那么第二個黑圓點運算就有形式(b,a)，但是黑圓點運算時一致的，因此兩個形式時一致的，因此a=b，所以有|S|=ab=a^2。

4. Reversibility of cellular automata

細胞自動機以及可逆細胞自動機的定義：

引理11：

如果一個細胞自動機可逆，那么它的逆也是細胞自動機。這是顯然的。

將h定義為一個對細胞自動機的映射運算，其就是將長度為2r的細胞自動機的狀態(tài)集合S=A^2r 的平方映射到一個S上。可以得到集合S與運算h可以成為一個群。

這段就是說明了可逆的細胞自動機剛好可以表示為一個半中心雙群，因此半中心雙群的方法可以很好的應用于研究可逆的細胞自動機。

5. Graph model

這一個部分，主要介紹了圖對于半中心雙群（一般的，不一定非得冪等）的一種等價模擬關(guān)系，這中對應關(guān)系在中心群內(nèi)也有體現(xiàn)。

5.1. Digraphs（有向圖）

在圖論中，有一個由有向圖所決定的問題是這樣的，每一對節(jié)點都是被一個單一的給定長度的路徑所連接的。這也被成為UUP_n。當n=1時，可以得到一個簡單完全圖且對于更長的路徑的情況，可以發(fā)現(xiàn)更多的結(jié)果類。

inter-prosessor communication 圖提出了一個問題。一個合適的解釋是，作者提出了一個雙色邊的有向圖，雙色分別是紅與藍，對于每一對節(jié)點(a,b)之間，存在一條直接的長度為2的紅-藍路徑，每個紅邊都跟這一個藍邊，且假設所有節(jié)點有一個任意顏色的回環(huán)。我們將這個稱之為unique 2-coloured 2-path graphs。

后面討論接下來的迭代。設一個關(guān)于績點的固定集合，從這個集合里著眼兩個方向的圖，一個是G_R，另一個是G_B，并各自稱之為紅圖與藍圖。問題是如何安排這些圖使得當我們將他們重疊在一起的時候，任意兩個點之間，都有一條唯一的長度為2的雙色（blue-red）路徑，和唯一的（red-blue）雙色路徑。我們可能需要假設所有節(jié)點的每種顏色的路徑都構(gòu)成循環(huán)，但這是沒必要的。我們必須允許同一節(jié)點對中存在兩個不同顏色的不同邊。因此，我們應該討論多重圖，因此多重圖類可以被稱為symmetric 2-coloured unique 2-path multigraphs。

圖1 是將每個節(jié)點的回環(huán)刪除之后的一對雙色路徑圖的示例。

這些例子的一個廣義類可以被簡單的構(gòu)建為方格（grid），將任意一個Z×Z中的一個矩形視作一個點集合，將所有的點用紅邊連接到一條平行線上，然后將所有的點也在一條垂直邊上用藍色的弧線連接。則為了得到沿著紅藍通路的從某個點到另一個點，首先從水平線上沿著紅邊到達對應的垂直線，然后沿著藍邊到達對應的點，類似于曼哈頓街道圖。如果要找藍紅邊則是將順序顛倒。

注意到這些圖的incidence matrices（關(guān)聯(lián)矩陣）有這樣的性質(zhì)：AB=BA=J，其中A,B是關(guān)聯(lián)矩陣，J是一個有1組成的矩陣。正如由Hoff'man提出和由Knuth研究的矩陣，對于0-1矩陣A如果有A^2=J是已經(jīng)被證明的。對于0-1矩陣A，是否有A^n=dI+入J，仍是一個有趣的問題。

5.2 Connections

在這一部分，作者將證明有循環(huán)邊的有向圖與冪等的代數(shù)結(jié)構(gòu)是等價的。

構(gòu)造12：

這個說的是，如果a點能通過一條紅（藍）邊到達b點，那么可以認為存在一個c點，使得a通過與c點一個黑（白）圓點運算得到b點，這就跟群聯(lián)系上了；然后通過加入一個中間點c，可以得到從a點通過紅（藍）邊到c_r（c_b）點，然后再通過一條藍（紅）邊到達b點，則定義a跟b的黑（白）圓點運算可以得到對應的c點，這就是一個代數(shù)結(jié)構(gòu)了。

推論10：

如果一個代數(shù)結(jié)構(gòu)是半中心雙群，那么上述的結(jié)構(gòu)可以定義一個對稱的雙色唯一雙路徑多圖。相似的，給定一個對稱雙色唯一雙路徑多圖，上述結(jié)構(gòu)也可以定義一個半中心雙群，這個結(jié)構(gòu)是可逆的。

對于推論10的證明是比較顯然的。

如果節(jié)點a是冪等的，所以有a黑圓點a=a，則有a節(jié)點有一個紅回環(huán)邊，同理藍回環(huán)邊也是一樣的。因此，如果S是冪等的，每一個節(jié)點都有一個回環(huán)邊，如上述的案例。

那么，假定兩個類，S是一個半中心雙群，G是一個對稱的雙色唯一雙路徑多圖。如果從S與G中的函子由上述構(gòu)造12描述，取S中的一個序列A->f B->g C。因為f，g兩個映射運算的是兩個半中心雙群中的元素，他們在函子下的圖節(jié)點中的運算，也可以攜帶邊。因此在圖G中range(f) = ker(g)，所以函子也是確定的（這一段是直譯，我的理解，可以結(jié)合上面定義的結(jié)構(gòu)來理解，將f看成黑圓點運算，g看成是白圓點運算）。那么我們得到如下結(jié)果：

引理13：

引理13說的是同構(gòu)的半中心雙群可以根據(jù)構(gòu)造12給出一個同構(gòu)的圖對。

因此，在圖對和半中心雙群是等價的，如下內(nèi)容可以說明一個半中心雙群的自同構(gòu)的群可以由一個相互連接的圖的自同構(gòu)群來得到，這在組合數(shù)學中已經(jīng)得到充分研究?！舅裕髡吣J讀這篇論文的人都了解組合數(shù)學嗎？？？暈~】

引理14：

這里說的是，如果G_b與G_r是由半中心雙群S定義的，那么有S的自同構(gòu)等于G_b的自同構(gòu)交G_r的自同構(gòu)。

證明如下：

因此，可以使用為確定圖的自同構(gòu)而開發(fā)的算法來輕松確定半中心雙群的自同構(gòu)群。這是一個特殊的問題，與后面關(guān)于半中心雙群提升的獨特性的結(jié)果有關(guān)，而且它在構(gòu)造我們將在第8節(jié)中研究的矩形結(jié)構(gòu)的例子中也具有相當大的價值。盡管可能有直接確定冪等半中心雙群的自同構(gòu)群的技術(shù)，但超越為確定圖自同構(gòu)而開發(fā)的高效算法所需的工作量可能相當高。

6.?Uniqueness of semicentral bigroupoids

在本節(jié)中，我們研究了同構(gòu)的概念和確定半中心雙群之間同構(gòu)的方法。這可以擴展到一種計數(shù)方法，這樣給定給定大小的冪等半中心雙群的詳盡列表，我們可以精確地計算存在多少個該順序的半中心雙群。二元性和對稱性再次使我們的工作更輕松。

引理15：

引理15說的就是，如果某個映射對于兩個半中心雙群中，如果對于其對應的某個運算對應的群是同構(gòu)映射，那么對于另一個運算也是同構(gòu)映射。證明還是比較清晰的，就是直接代入運算。

通過這個引理，我們可以看到任何一個半中心雙群都是一個冪等的半中心雙群的“l(fā)ifting”。此外還有：

引理16：

引理16指的是每一個半中心雙群都與一個矩形結(jié)構(gòu)相聯(lián)系且在"lifting"中都是固定過程。

推論11：

推論11說明了，兩個半中心雙群的同構(gòu)性與其相聯(lián)系的矩形結(jié)構(gòu)的同構(gòu)性一致。

充分性的證明方式就是給定兩個同構(gòu)的半中心雙群，然后分別對其對應的矩形結(jié)構(gòu)進行同構(gòu)運算，如果可以通過一個矩形結(jié)構(gòu)可以用這一個同構(gòu)運算得到另一個；然后通過該同構(gòu)運算的逆運算，再做一次運算，如果可以推出原來的矩陣結(jié)構(gòu)，則證明完畢。

必要性的證明則是證明同構(gòu)映射可以保持關(guān)聯(lián)的矩形結(jié)構(gòu)，如上。

推論11告訴我們，一個給定一類非同構(gòu)的矩形結(jié)構(gòu)，我們是無法得到同構(gòu)的冪等半中心雙群的，反之亦然。矩形結(jié)構(gòu)跟冪等的半中心雙群是完全等價的。

上述的圖論沒有提及冪等的條件，因此作者在后續(xù)考察了非冪等半中心雙群有啥性質(zhì)。

推論12：

推論12介紹了，兩個同構(gòu)的半中心雙群，其同構(gòu)映射已知。當且僅當他們的冪等"lifting"與同構(gòu)映射是同構(gòu)的，且其各自的平方映射滿足上述等式。

證明：

充分性，通過已知的冪等"lifting"計算和給定的同構(gòu)映射代入做運算，最后得出等式取逆即可證明；必要性，對兩個半中心雙群中的一個，代入一個冪等"lifting"的運算及其逆運算和做同構(gòu)映射，進而可以計算出同構(gòu)映射與冪等"lifting"的結(jié)合可以得到另一個半中心雙群的同構(gòu)映射與冪等"lifting"，然后冪等"lifting"的逆運算與后面的式子結(jié)合得到證明開頭定義的式子。通過將同構(gòu)映射代入的操作，得到（89）式子，進而從新運用開頭定義的式子，得到（90）式子，然后剛好出現(xiàn)一個冪等"lifting"及其逆運算，可以消去，得到最終結(jié)果。證畢。

緊接著，作者開始提到Symm(S)這個S上的對稱組的性質(zhì)，Symm_RS(S)是矩形結(jié)構(gòu)(S,黑圓點,白圓點)這個半中心雙群上矩形結(jié)構(gòu)的一個對稱組，定義[a,b]=aba_(-1)b_(-1)是Symm(S)中關(guān)于a,b的置換(permutation)。

引理17：

引理17給出了半中心雙群的同構(gòu)"lifting"的充分必要條件。

證明

推論13：

推論13說明，冪等半中心雙群的兩個"lifting"是同構(gòu)的，當且僅當兩個"lifting"是由Symm_RS(S)中的一個元素共軛的。

證明：

為了將一些特定規(guī)模的半中心雙群進行分類，僅需要決定該規(guī)模的矩形結(jié)構(gòu)，找出其對稱組，取其在Symm_RS(S)的Symm(S)中的共軛類。

7. Counting semicentral bigroupoids

在這一小節(jié)，作者舉例說明了如何數(shù)出一個給定的冪等半中心雙群的非同構(gòu)"lifting"的數(shù)量。

給定一個矩形結(jié)構(gòu)R，可以找到它的對稱組 G = Symm(R) < Symm(S)。這一性質(zhì)可以通過引理14中的圖模型找出冪等半中心雙群的自同構(gòu)群。這些Symm(S)上的自同構(gòu)行為是共軛的。從前面的內(nèi)容中，每個與一個在矩形結(jié)構(gòu)R上的半中心雙群"lifting"的一個同構(gòu)類與一個orbit相對應。因此，問題變?yōu)榱巳绻麛?shù)出orbit的數(shù)量。

作者將這一個問題構(gòu)建成就組置換的問題。讓G:=S_n 對于一些n，并且去一些子組K<=G。則使得G由在K下同構(gòu)的orbit的數(shù)量，可以通過Burnside的引理得到：

其中，t是orbit的數(shù)量，F(xiàn)_G(k)是由k所固定的G的元素的集合。但這僅僅只是G中的k的一個中心化。

如果我們著眼于G與其自身的共軛操作，通過數(shù)出子群C_G(k)的合集，可以得到：

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

可以知道Gk是與k共軛的所有G元素的集合，且這個集合與k有著相同的圓圈結(jié)構(gòu)。如果k有一個長度為a_i的t_i圓圈的圓結(jié)構(gòu)，包括長度為1的圓，那么有：

引理18：

證明：

由于G的數(shù)量關(guān)系與引理18可知：

通過計算每一個k屬于K的元素的|C_G(k)|之和，可以得到orbit的數(shù)量如下：

推論14：

這個結(jié)論給出了同構(gòu)的非唯一性。給定一個矩形結(jié)構(gòu)或者相對的冪等半中心雙群，可以輕易的計算其對稱組，并決定其非同構(gòu)"lifting"對的數(shù)量。

8. Generationg rectangular structures

作者研究了使用增量過程全面構(gòu)建具有給定格式的所有示例的方法。這些方法利用內(nèi)部對稱性和其他結(jié)構(gòu)來顯著減少搜索空間，并避免或刪除同構(gòu)示例。所研究的方法是兩階段方法，生成然后刪除同構(gòu)副本。然后，我們看看另一種方法，該方法通過跟蹤生成樹中可能的分支來僅生成非同構(gòu)示例。我們比較這兩種算法，看看哪個更古老。所有技術(shù)都使用分支生成樹來逐個生成示例。trade-o介于增加生成樹算法的復雜性和增加努力以刪除生成的列表中的同構(gòu)副本之間。

在這個小節(jié)，作者提出了各種偽代碼算法。

8.1 Partial rectangular structures

這一部分，作者提出了窮舉所有特性形式矩形結(jié)構(gòu)的方法。這個方法是通過從更簡單的非完全樣例中構(gòu)建出樣例，在分支處理中，每個不完全樣例可以被許多不同的方式構(gòu)建出來。這些方法被提出去通過僅僅使用規(guī)范的外延，正向的一部晚宴和一場同構(gòu)外延，來減少非必要的分支。然后，我們研究對列表進行排序的技術(shù)，篩選出重復項。此處的定義也與其他技術(shù)相關(guān)。

定義15-17：

可以看到一個矩形結(jié)構(gòu)是一個部分矩形結(jié)構(gòu)。部分矩形結(jié)構(gòu)可以通過公式（25）的覆蓋要求來生成矩形結(jié)構(gòu)。一個全部分矩形結(jié)構(gòu)擁有nm個矩形。這是一個矩形結(jié)構(gòu)。

樣例：

我們可以得到一個帶有兩個矩形的部分矩形結(jié)構(gòu)。這個矩形還可以是上述序列的一個最小的矩形，且可以加到其他前面的矩形。

我們可以通過字典排序來排列矩形來排序同樣規(guī)模的部分矩形結(jié)構(gòu)。這在一個代數(shù)的計算機語言如GAP中應用算法是是否有用的，其中集合被定義成無重復的有序列表。算法預先定義的結(jié)構(gòu)集合也因此在系統(tǒng)上沒有額外的負擔。

將S_nm這一個在{1,...,nm}上的對稱組，自然的作用部分矩形結(jié)構(gòu)。

定義18：

定義19：

8.2 Algorithems

自此，我們可以得到一個自然算法。假設一個函數(shù)pos_noe_ext(P)，給定一個部分矩形結(jié)構(gòu)P，可以返回所有可以加上P形成一個正向單步外延的矩形的集合。通過深度有心啊分支樹聚集最小部分矩形結(jié)構(gòu)(112)的所有擴展的完整列表，然后再S_mn下取orbit并且在每個orbit中選擇最小的滿部分矩形結(jié)構(gòu)，就會形成一個簡單但是效率比較低的算法。

一個更加有效率的辦法必須要檢查當前部分矩形結(jié)構(gòu)中同構(gòu)的方面并且僅僅拓展其中代表性的一個，試圖避免多條導向同一個矩形結(jié)構(gòu)的通路。

作者僅僅需要考慮一些對于部分矩形結(jié)構(gòu)的外延，因為他們僅需要具有代表性的滿菊粉矩形結(jié)構(gòu)和有代表性的矩形結(jié)構(gòu)。

推論20：

任何一個代表性的部分矩形結(jié)構(gòu)是一個代表性的部分矩形結(jié)構(gòu)的正向單步外延。

證明：

【時隔許久的吐槽，從第五節(jié)開始，這個作者就在瘋狂甩設定，然后瘋狂自己的設定之間存在等價關(guān)系；然后，每個概念都是提出來但是不好好說明，閱讀難度驟增...】

注意到，這部是意味著代表性的單步正向外延是必要的，或者部分矩形結(jié)構(gòu)P的單步正向外延總是P的代表。這個允許我們?nèi)タs減許多搜索樹的分支，因為任何一個部分蛛形結(jié)構(gòu)如果不是代表性的則不可能是我們的目標，并且也沒有必要去延展它。

然后，作者根據(jù)這個提出了他的算法：

算法：

【這個偽代碼比較簡單，但是其中有一些操作還是需要理解一下，如：Aut(P)，以及怎么取G下的S的Orbit，還有find_all_rs(Union(P,{rep}))是啥意思，需要跟上面的論述內(nèi)容結(jié)合才能理解...】

作者讓所有的候選項都便利知道他們成為矩形結(jié)構(gòu)而不是使用額外的對非完全部分矩形結(jié)構(gòu)的額外測試，然后通過測試樣例之間的同構(gòu)性來拒絕同構(gòu)項，這一個技術(shù)會在下一個部分介紹。相似的證明表明，圖、部分代數(shù)和部分矩形結(jié)構(gòu)自同構(gòu)都是等價的。

定義21：

引理19：

證明：

定理22：

證明：

這一段直接就放原文了，證明分了三個部分，第一個是部分矩形結(jié)構(gòu)P只有一個元素時，直接成立，然后當P有k+1個時，可以從推論20中得到其代表性的P’，因此可以被算法找到。

因此，這個算法的結(jié)果列表時完全的。后續(xù)的部分分為篩選列表中同構(gòu)的。然后找一個可以進一步減少生成樣本的數(shù)量的技術(shù)。

8.3 Sieving the full partial rectangular structures

上述算法已經(jīng)可以找到一大批矩形結(jié)構(gòu)，但是即便該算法已經(jīng)極大的縮減了分支，但是仍然無法了解是否有所有成對的非同構(gòu)，如果這些例子時代表性的。傳統(tǒng)的辦法會導致難以克服的空間復雜度，因此需要一個更有效率的辦法。

由于矩形結(jié)構(gòu)與圖對（帶循環(huán)）是等價的因此，兩個矩形結(jié)構(gòu)之間的同構(gòu)問題等價于兩個帶循環(huán)的圖對之間是否痛毆。圖的所有節(jié)點都有循環(huán)邊，因此在決定同構(gòu)性的時候可以忽略。圖同構(gòu)在圖理論上是一個成熟的問題，可以有一個有效率的算法計算圖同構(gòu)。

算法偽代碼如下：

這個算法也是比較直接的，直接口語化的表述，因此直接原文。其中需要理解的就是看看怎么從矩形RS里計算graphpair。

作者還提到，盡管這個辦法已經(jīng)簡化了很多復雜度，但是仍可以通過組合的性質(zhì)來進一步簡化，因為這可以避免判斷圖的同構(gòu)性?？梢詫蓚€圖結(jié)合成一個圖，兩個圖對的同構(gòu)性與兩個結(jié)合圖的同構(gòu)性是等價的。如果(A,B)在點集合{1,...,n}上的圖對，那么利用標簽a和b可以湊早一個新的圖，節(jié)點和邊如下：

可以看到，從兩個圖對構(gòu)造的圖是同構(gòu)的當且僅當兩個圖對是同構(gòu)的。

8.4 Prohibited extension

【讀到這里，人已經(jīng)麻了~讀后忘了前面，加上最近事情實在是多...斷斷續(xù)續(xù)在讀，快扛不住了，都是一些新概念，T_T】

算法find_allrs生成了許多非代表的樣例，接下來的結(jié)果讓我們能夠避免許多已知被其他地方生成的外延。

推論23：

推論23說的就是一個代表性的部分矩形結(jié)構(gòu)P，如果存在一個矩形R使得其與P的并不是代表的，但是存在一個映射關(guān)系可以是其成為代表的，那么存在一個j可以使得P‘的映射關(guān)系運算之后還得到其本身，映射關(guān)系屬于P’的共軛，且P'并映射R是一個P‘的正向單步外延映射R<R_(j+1)。

為了使用這個結(jié)果，作者遞歸地傳遞部分矩形結(jié)構(gòu)，并帶有收集prohibited的擴展。如果R<T是矩形且是最小的一個部分矩形結(jié)構(gòu)P的正向單步外延，那么Aut(P)(R)是被加入P∪{T}的prohibited集合。

這要求計算Aut(P)(R)時沒有額外的時間花銷。而且，減少分支在也會減少篩選同構(gòu)樣例的時間花銷。

8.5 Orderly algorithms

一個保障分支生成不會生成同構(gòu)樣例的可選辦法，因此刪除算法的篩選步驟。通過仔細地bookkeeping，這是可以實現(xiàn)的。這些生成步驟已經(jīng)被成為"orderly"。

這個部分介紹了Royle的辦法，然后描述了算法的必要功能。我們那么找組合的特質(zhì)取加速算法。

設V是一個集合，G=Aut(V)。我們將在v∈V上的g∈G的行為和自然而然的延拓到集合上的行為寫為v^g。作者想要找到所有的子集X包含于V使得P(X)對于一些P的遺傳性質(zhì)是真的，但是他們只想要一個從每個同構(gòu)類中的一個樣例，同構(gòu)性被定義為G。

我們需要一個函數(shù)Θ使得：

Θ: 2^V?-> 2^V，

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

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

G_X是X的一個穩(wěn)定，G_X={g∈G|X^g=X}。

讓T_k是規(guī)模為k的集合個一個集合，使得P(X)對于所有的X都有X∈T_k，且T_k不包含任何同構(gòu)。作者提出了從T_k中產(chǎn)生T_(k+1)集合的一個算法：

算法偽代碼：

這個代碼，最關(guān)鍵的就是理清各個符號的意思，算法本身不難。

定理24：

定理24說，如果T_k只包含一個V的k-集合的G-orbit的代表且擁有P的性質(zhì)。那么有算法產(chǎn)生的T_(k+1)集合也是只包含一個V的k+1-集合的G-orbit的代表且擁有P的性質(zhì)。

從T_0={?}開始，用一個orderly算法取構(gòu)建一個帶有P性質(zhì)的V的子集的一個代表。這就是我們定義的函數(shù)Θ。

定義25：

這意味著如果我們在圖的自同構(gòu)組下取最小的規(guī)范化標簽指向圖的orbit，那么無論我們怎么重新標記這個圖這個orbit都是唯一確定的。這也是形成了我們定義Θ的一個機制。

我們的狀況是這樣的，集合V是一個n×m的矩陣的集合，P是成為一個部分矩形結(jié)構(gòu)的性質(zhì)。我們想要找出全部分矩形結(jié)構(gòu)的集合T_nm，也是矩形結(jié)構(gòu)。

讓花體R是一個部分矩形結(jié)構(gòu)，R∈花體R是被考慮的外延。Θ必須從花體R上的G_R中選擇一個orbit，想要了解R∈Θ(花體R)是否成立。首先通過組合值來進行選擇。一個組合值v:V×2^V->Z是一個G的orbit上的常數(shù)，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是最小的但是不唯一，那么我們用規(guī)范化標簽從花體R的圖中的集合{dQ:Q∈R}上選擇最小的標簽元素m，且讓Θ(花體R)=m^(G_R)。如果R是在這個orbit中的，我們就遞歸，否則我們就不繼續(xù)這個外延。

8.6 Results

【只能說Finally，讀到這里，我人都暈了~全是概念，群、半中心雙群、orbit、圖、矩形結(jié)構(gòu)、部分矩形結(jié)構(gòu)、全部分矩形結(jié)構(gòu)、矩形...】

時間對比這部分就不介紹了~可以自己看論文...放上對細胞自動機的結(jié)果

關(guān)于結(jié)果表格，B站最多上傳100張圖片，因此我沒放，可以自己到論文里看...

其中：

Size列表示的是狀態(tài)數(shù)量，Idempotents列是所有靜止狀態(tài)規(guī)則的數(shù)量，Lifting列是非重復規(guī)則的總數(shù)。只有一個平凡細胞自動機規(guī)則(保持和左右移動，帶"lifting")，形式是1×x和x×1，所以這些被忽略了。作者還忽略了很多其他情況，可以看原文去了解。

9.conclusion

還說啥呢？就是提出了一個新辦法，然后論證了這個辦法的有效性，提出了可以應用這個方法的普通算法，然后通過引入多個領(lǐng)域的理論，優(yōu)化了這個算法。

【文末】

吐槽：

讀完這個論文，感覺就是這個論文閱讀難度還是挺高的，如果對于一些代數(shù)學上的概念不太清楚，真的會看不懂，然后作者還自己定義了許多內(nèi)容，每個內(nèi)容之間的引用都不是緊接著的，而是興致到了就告訴我這個結(jié)論是基于前面提到的某個內(nèi)容，這時就需要你不斷翻頁去看這個，然后思考怎么把這個應用到這里。然后作者的證明，基本上都是一些代入計算，如果對某些他自己定義的東西或者運算的理念不了解，根本證明不下去~雖然作者用了細胞自動機做題目，但是通篇內(nèi)容，都沒有太使用細胞自動機的語言，而是完全通過代數(shù)相關(guān)的內(nèi)容來行文，因此即便是細胞自動機相關(guān)領(lǐng)域的人來看這個論文，也沒有多少熟悉度。有時候，看著這個論文，連翻譯都很困難，因為很多都是數(shù)學名詞，實在是不熟悉。這篇論文就是屬于曲高和寡的那一類文章...

作者提出的偽代碼，根本就是純口語表達，計算細節(jié)是一點都不提供，不過提到了一些語言包的實現(xiàn)方法...我沒有特別去提。

我的感受就是作者寫的比較碎，屬于我需要哪個概念了，就提出來，然后進行論證，論證之后我就在后面某個地方引用，但是引用方式基本都是告訴你這倆概念是等價的，可以通過某個運算方式轉(zhuǎn)化的。

深刻感受到了B站對轉(zhuǎn)欄對這類稿件編輯的不便，根本不提供公式內(nèi)容的編輯渠道（也可能是我不太會用），后續(xù)內(nèi)容可能會轉(zhuǎn)移到知乎啥的，當然如果有視頻稿件會及時進行更新...

心得：

本文作者通過首先定義了半中心雙群，然后提出冪等的半中心雙群，然后通過證明矩形結(jié)構(gòu)跟圖對(紅藍雙路徑)與冪等半中心雙群的等價性，以及可逆細胞自動機與冪等半中心雙群的等價性，將細胞自動機問題轉(zhuǎn)化成代數(shù)結(jié)構(gòu)上的問題。

然后繼續(xù)引入新的概念，部分矩形結(jié)構(gòu)，以及全部分矩形結(jié)構(gòu)，然后通過同構(gòu)映射將這些內(nèi)容聯(lián)系起來，把問題又變成了找圖上的同構(gòu)對啥的，進一步簡化了問題。

在結(jié)果上，作者嘗試了多狀態(tài)的細胞自動機，并且號稱窮盡了可逆一維細胞自動機。