元胞自動機/決策問題

對一維 CA 決策問題的研究基於德布魯因圖的子集圖。子集圖被解釋為一個有限自動機，並據此進行分析。大多數決策問題都是使用較大的矩陣子集圖來定義的，但它們可以使用較小的向量子集圖重新定義。

子集圖

子集圖中的節點是所有可能的原像矩陣或向量，它們可以使用布林元素來寫。

矩陣子集圖

矩陣子集圖是一個有向圖 $\langle S,Q_{D},\delta _{D}\rangle$ 後來被改造成一個有限自動機。

$Q_{D}$ 是所有狀態的集合，它們都是$|Q_{D}|=2^{k^{2(m-1)}}$ 個不同的布林原像矩陣。

$Q_{D}=\left\{{\begin{bmatrix}0&0&\dots 0\\0&0&\dots 0\\\vdots &\vdots &\ddots \vdots \end{bmatrix}},{\begin{bmatrix}1&0&\dots 0\\0&0&\dots 0\\\vdots &\vdots &\ddots \vdots \end{bmatrix}},\dots ,{\begin{bmatrix}1&1&\dots 1\\1&1&\dots 1\\\vdots &\vdots &\ddots \vdots \end{bmatrix}}\right\}$

可用細胞狀態的集合$S$ 用於連結標籤以及作為自動機的字母表。自動機的狀態轉換函式 $\delta$ 定義了狀態之間及其標籤之間的連結。

$\delta _{D}:Q_{D}\times S\rightarrow Q_{D}$

可以構建兩個轉移函式，一個用於正向方向 $\delta _{D,f}$，另一個用於反向方向 $\delta _{D,b}$。輸入符號 $c\in S$ 上的轉移由單單元前像矩陣定義。

$q_{D_{x+1}}=\delta _{D,f}(q_{D_{x}},c_{x})\qquad D_{x+1}=D_{x}\cdot D(c_{x})\quad {\mbox{boolean multiplication}}$

$q_{D_{x-1}}=\delta _{D,b}(q_{D_{x}},c_{x})\qquad D_{x-1}^{T}=D(c_{x-1})\cdot D_{x}^{T}\quad {\mbox{boolean multiplication}}$

從圖 $\langle S,Q_{D},\delta _{D}\rangle$ 中構建一個有限自動機 $\langle S,Q_{D},q_{0},\delta _{D},F_{D}\rangle$，透過指定初始狀態 $q_{0}\in Q_{D}$ 和最終狀態集 $F_{D}\subset Q_{D}$。

空集 是狀態 $q=0$，其中所有前像矩陣元素都是 0。

${\begin{bmatrix}0&0&\dots 0\\0&0&\dots 0\\\vdots &\vdots &\ddots \vdots \end{bmatrix}}$

向量子集圖

向量子集圖是一個有向圖 $\langle S,Q,\delta \rangle$，後來被改造為一個有限自動機。 $Q$ 是所有狀態的集合，這些狀態都是 $|Q|=2^{k^{m-1}}$ 個不同的布林原像向量。

$Q_{b}=\{0,1,\dots ,b,\dots ,|Q|-1\}$

$q=\sum _{o=0}^{k^{m-1}-1}b(o)=2^{k^{m-1}-1}b(k^{m-1}-1)+\cdots +2^{o}b(o)+\cdots +2b(1)+b(0)$

可用細胞狀態的集合$S$ 用於連結標籤以及作為自動機的字母表。自動機的狀態轉換函式 $\delta$ 定義了狀態之間及其標籤之間的連結。

$\delta :Q\times S\rightarrow Q$

可以構建兩個轉移函式，一個用於正向方向 $\delta _{f}$，另一個用於反向方向 $\delta _{b}$。在輸入符號 $c\in S$ 上的轉換由單個單元格的原像矩陣定義。

$q_{x+1}=\delta _{f}(q_{x},c_{x})\qquad b_{x+1}=b_{x}\cdot D(c_{x})\quad {\mbox{boolean multiplication}}$

$q_{x-1}=\delta _{b}(q_{x},c_{x})\qquad b_{x-1}^{T}=D(c_{x-1})\cdot b_{x}^{T}\quad {\mbox{boolean multiplication}}$

有限狀態自動機 $\langle S,Q,q_{0},\delta ,Q_{F}\rangle$ 是從圖 $\langle S,Q,\delta \rangle$ 構建的，透過指定一個初始狀態 $q_{0}\in Q$ 和一組最終狀態 $Q_{F}\subset Q$.

空集 是狀態 $q=0$，其中原像向量 $b$ 中沒有重疊可以用來追蹤路徑。

$b=[0,0,\dots ,0]$

全集 是狀態 $q=2^{k^{m-1}}$，其中原像向量 $b$ 中的所有重疊都可以用來追蹤路徑。

$b=[1,1,\dots ,1]$

判定問題

為了觀察判定問題，子集圖被轉換成一個自動機。一個被定義為一系列單元格的詞 $\alpha$ 被接受，如果它將指定的初始狀態連線到一個最終狀態。

德布魯因子集圖用於回答單射和滿射問題、原像的正則表示式......

CA規則的滿射性

如果每個當前配置 $C^{t}$ 至少有一個原像 $C^{t-1}$，則全域性轉移函式是滿射的。

$\forall C^{t}\;\exists C^{t-1}\;:\;F(C^{t-1})=C^{t}$

由於前像是在前像網路中的路徑，因此在任何細胞字串 $\alpha$ 的邊界之間，必須至少存在一條路徑。

最短的未被接受的字串

與子集圖相關的另一個問題是，子集圖中未被接受的最短字串。這可以很容易地重新表述為一個判定問題：子集圖是否具有長度為 $l$ 或更短的字串，對於給定的整數 $l$。根據這個問題的定義，對於給定的元胞自動機規則和給定的 $l$ 測試為真，相同的元胞自動機將對於 l+1 測試為真。如果元胞自動機是滿射的，那麼就不會存在這樣的字串。

沃爾夫勒姆暗示，薩特納所說的 1-置換元胞自動機很可能對於具有相同字元數量和相同寬度的元胞自動機集合中最高的 $l$ 測試為假。金斯伯裡在他的本科論文中證明，1-置換 CA 將對於所有大於或等於 $wk^{w-1}$ 的 $l$ 測試為真，其中 $w$ 是 CA 的寬度，$k$ 是符號的數量。假設這對所有 CA 都是正確的（沃爾夫勒姆和薩特納的工作似乎表明應該如此），這確保了該判定問題的任何證書可以在時間複雜度為 CA 規則表大小的多項式時間內被驗證。目前尚不清楚是否可以在多項式時間內構建這樣的證書。

定理：寬度為 $w$，在 $k$ 個符號上的 1-置換 CA，其最短的未被接受的字串的長度不超過 $wk^{w}-1$。

證明：待定

定義和證明

布林矩陣和向量運算

所有數學加法和乘法都被替換為其布林對應物析取和合取。

加法變為析取（邏輯運算子 OR）

$x_{1}+x_{2}\to x_{1}\lor x_{2}$

乘法變為合取（邏輯運算子 AND）

$x_{1}\cdot x_{2}\to x_{1}\land x_{2}$

然後使用這些基本的布林運算來定義矩陣和向量運算。

參考文獻

1. Tobias Gärtner, Timo von Oertzen 和 Jan Schwinghammer，高效計算正則語言的密度，拉丁美洲資訊學會議 (LATIN'04) 論文集，第 262-270 頁，布宜諾斯艾利斯。
2. Etienne Grandjean，幾乎所有有限結構的一階理論的複雜度，資訊與控制，第 57 卷（第 2/3 期）：180-204 頁，1983 年 5 月/6 月。

工具

1. Grail+