元胞自动机/决策问题

对一维 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+