无立方态态射与线性多状态变量元胞自动机研究

### 无立方态态射与线性多状态变量元胞自动机研究 #### 无立方态态射测试集 在研究无立方态态射时，我们关注的是从字母表 $A$ 到字母表 $B$ 的无立方态态射的测试集。若 $|B| = 1$，从 $A$ 到 $B$ 的唯一无立方态态射是空态射 $\epsilon$（当 $|A| = 1$ 时还有恒等态射 $Id$），后续我们假设 $|B| \geq 2$。 一个单词集合 $T$ 是从 $A$ 到 $B$ 的无立方态态射的测试集，当且仅当对于任意从 $A$ 到 $B$ 的态射 $f$，$f$ 是无立方态的当且仅当 $f(T)$ 是无立方态的。 首先，当 $|A| \geq 3$ 时，有如下定理： - **定理 3**：给定两个字母表 $A$ 和 $B$，其中 $|A| \geq 3$ 且 $|B| \geq 2$，不存在从 $A$ 到 $B$ 的无立方态态射的有限测试集。 该定理是下面命题 1 的推论。设字母表 $A$ 至少包含两个字母，取 $A$ 中的一个特定字母 $a$，以及三个不属于 $A \setminus \{a\}$ 的不同字母 $x$、$y$、$z$。令 $C = A \setminus \{a\} \cup \{x, y, z\}$，$u$ 和 $v$ 是 $A \setminus \{a\}$ 上不同时为空的无立方态单词。定义态射 $f_{u,v} : A^* \to C^*$ 如下： \[ f_{u,v}(a) = xzyuxyvxzyuxyvxzy \] \[ f_{u,v}(b) = b, \text{ 对于所有 } b \in A \setminus \{a\} \] - **命题 1**：设 $w$ 是 $A$ 上的无立方态单词，$f_{u,v}(w)$ 是一个立方的最小覆盖当且仅当 $w = avaua$。 **定理 3 的证明**：考虑 $A$ 中的一个特定字母 $a$，令 $C = A \setminus \{a\} \cup \{x, y, z\}$。由于 $|A| \geq 3$ 且 $|B| \geq 2$，根据定理 1，存在从 $C$ 到 $B$ 的无立方态态射 $g$。由命题 1 可知，对于 $A \setminus \{a\}$ 上不同时为空的两个单词 $u$ 和 $v$，$g \circ f_{u,v}(w)$ 是一个立方的最小覆盖当且仅当 $w = avaua$。因此，$avaua$ 属于从 $A$ 到 $B$ 的无立方态态射的任何测试集的因子集。由于 $A \setminus \{a\}$ 上有无穷多个无立方态单词，所以从 $A$ 到 $B$ 的无立方态态射的任何测试集都是无限的。 接下来，假设 $|A| = 2$，例如 $A = \{a, b\}$。$\{b\}$ 上的无立方态单词 $u$ 和 $v$ 只能取三个值 $\epsilon$、$b$ 和 $bb$。使用与定理 3 证明类似的技术，考虑 $(u, v)$ 为 $\{(bb, bb), (b, bb), (bb, b), (\epsilon, bb), (bb, \epsilon), (b, b)\}$ 时的 $f_{u,v}$ 和 $f_{u,v} \circ E$，作为命题 1 的另一个推论，对于从 $\{a, b\}$ 到基数至少为 2 的字母表的任何无立方态态射的测试集 $T$，$T$ 的因子集包含： \[ T_{min} = \{abbabba, baabaab, ababba, babaab, abbaba, baabab, aabba, bbaab, abbaa, baabb, ababa, babab\} \] - **定理 4**：$\{a, b\}^*$ 的一个子集 $T$ 是从 $\{a, b\}$ 到基数至少为 2 的字母表的无立方态态射的测试集，当且仅当 $T$ 是无立方态的且 $T_{min} \subset Fact(T)$。 在证明该定理之前，先看一些特定的测试集。显然，$T_{min}$ 是其中之一。由于它包含 12 个元素，我们可以寻找最小基数的测试集。存在一些测试单词（即基数为 1 的测试集），例如，无立方态单词 $aabbababbabbaabaababaabb$ 是长度为 24 的满足定理 4 条件的 56 个单词之一，因此它是 $\{a, b\}$ 上无立方态态射的测试集，并且这个单词的长度是最优的，因为长度为 23 的无立方态单词不可能包含 $T_{min}$ 中的所有单词作为因子。 - **推论 1**：给定一个二元字母表上的态射 $f$，以下断言等价： 1. $f$ 是无立方态的。 2. 所有长度为 7 的无立方态单词的像都是无立方态的。 3. 所有长度至多为 7 的无立方态单词的像都是无立方态的。 为了证明定理 4，由于恒等态射是无立方态的，任何无立方态态射的测试集必然是无立方态的。所以，只需证明如果对于一个无立方态单词集合 $T$ 有 $T_{min} \subset Fact(T)$，那么 $T$ 是无立方态态射的测试集。将 $\{a, b\}$ 上长度至少为 8 的无立方态单词集合记为 $G_8$，长度至多为 7 的无立方态单词集合记为 $L_7$，定理 4 的证明分为两部分： - **命题 2**：对于 $G_8$ 中的任何单词 $w$，如果 $f(T_{min})$ 是无立方态的，那么 $f(w)$ 不是一个立方的最小覆盖。 - **命题 3**：如果 $f(T_{min})$ 是无立方态的，那么 $f(L_7)$ 是无立方态的。 命题 2 意味着如果 $f(T_{min})$ 是无立方态的，并且对于一个无立方态单词 $w$，$f(w)$ 包含一个立方，那么 $w$ 中属于 $L_7 \setminus Fact(T_{min})$ 的一个因子必然是这个立方的最小覆盖。命题 3 则证明了这种情况是不可能的。由于 $\{a, b\}^* = L_7 \cup G_8$，从这两个命题可以得出，$f(T_{min})$ 无立方态意味着 $f$ 是无立方态的。因此，如果 $T$ 是无立方态的且 $T_{min} \subset Fact(T)$，$T$ 是无立方态态射的测试集。 #### 命题 2 证明思路 命题 2 的证明采用反证法。假设 $G_8$ 中一个单词的像 $f(w)$ 是一个立方的最小覆盖，我们要证明至少 $f(T_{min})$ 中的一个单词包含一个立方。为此，需要更精确地研究当 $f(w)$ 是一个立方 $u^3$ 的最小覆盖时，立方 $u^3$ 的分解情况。 设 $w$ 的长度为 $n$，根据定义，单词 $w$ 的像 $f(w)$ 是一个立方 $uuu$ 的最小覆盖当且仅当 $f(w) = p_1uuus_n$，其中 $f(w[1]) = p_1s_1$，$f(w[n]) = p_ns_n$，$p_1$、$s_1 \neq \epsilon$、$p_n \neq \epsilon$ 和 $s_n$ 是一些单词。在这种情况下，存在两个介于 1 和 $n$ 之间的整数 $i$ 和 $j$，使得 $|f(w[1..i - 1])| < |p_1u| \leq |f(w[1..i])|$ 且 $|f(w[1..j - 1])| < |p_1uu| \leq |f(w[1..j])|$。 在命题 2 的证明中，当长度至少为 8 的无立方态单词的像 $f(w)$ 是一个立方的最小覆盖时，必然有 $1 < i < j < n$。此时，存在一些单词 $p_i$、$p_j$、$s_i$、$s_j$ 使得 $f(w[