遗传历史保持双模拟不可判定性及图扩张器问题近似难度研究

### 遗传历史保持双模拟不可判定性及图扩张器问题近似难度研究 #### 遗传历史保持双模拟不可判定性 在研究遗传历史保持双模拟（Hhp - Bisimilarity）的可判定性时，采用了从原点受限平铺系统的多米诺双模拟判定问题进行归约的方法。对于每个原点受限平铺系统 $T$，定义了一个异步转换系统 $A(T)$。 - **异步转换系统 $A(T)$ 的定义** - **事件集合**：$E_{A(T)} = \{x_i, y_i : i \in \{0, 1, 2, 3\}\} \cup \{d_{ij}, \hat{d}_{ij} : i, j \in \{0, 1, 2\}, d \in D$，且若 $(i, j) = (0, 0)$ 则 $d \in D_{ori}\}$。 - **标记函数**： $\lambda_{A(T)}(e) = \begin{cases} e & \text{若 } e \in \{x_i, y_i : i \in \{0, \ldots, 3\}\}\\ \lambda(d)_{ij} & \text{若 } e = d_{ij}, \text{ 对于某些 } d \in D\\ \lambda(\hat{d})_{ij} & \text{若 } e = \hat{d}_{ij}, \text{ 对于某些 } \hat{d} \in D \end{cases}$ - **状态、事件和转换**：可从图 1 中读取。图 1(a) 结构底层有十六个状态，可与图中垂直宏箭头上的数字对对应。对于每个状态 $(i, j)$ 和多米诺骨牌 $d \in D$，有 $d_{ij}$ 和 $\hat{d}_{ij}$ 事件转换。状态 $(0, 0)$ 是初始状态且特殊，只有来自原点约束 $D_{ori}$ 的多米诺骨牌可作为从此状态出发的转换事件。从 $d_{ij}$ 事件转换的两端，分别有 $x_i$ 事件转换到 $(i \oplus 1, j)$ 状态，$y_i$ 事件转换到 $(i, j \oplus 1)$ 状态，其中 $i \oplus 1 = i + 1$（若 $i < 3$），$i \oplus 1 = 2$（若 $i = 3$）。 - **独立性关系**：$I_{A(T)} \subseteq E_{A(T)} \times E_{A(T)}$ 是以下集合的对称闭包： - $\{(x_i, y_j), (x_i, d_{ij}), (y_j, d_{ij}) : i, j \in \{0, \ldots, 3\}, \text{ 且 } d \in D\}$ - $\{(d_{ij}, \hat{d}_{ij}) : i, j \in \{0, 1, 2\}, \text{ 且 } d \in D\}$ - $\{(d_{0j}, e_{1j}) : j \in \{0, 1, 2\}, \text{ 且 } (d, e) \in H_0\}$ - $\{(d_{ij}, e_{(i + 1)j}) : i \in \{1, 2\}, j \in \{0, 1, 2\}, \text{ 且 } (d, e) \in H\}$ - $\{(d_{i0}, e_{i1}) : i \in \{0, 1, 2\}, \text{ 且 } (d, e) \in V_0\}$ - $\{(d_{ij}, e_{i(j + 1)}) : i \in \{0, 1, 2\}, j \in \{1, 2\}, \text{ 且 } (d, e) \in V\}$ - **命题 12 证明思路** 命题 12 表明，存在关联原点受限平铺系统 $T_1$ 和 $T_2$ 的多米诺双模拟，当且仅当存在关联异步转换系统 $A(T_1)$ 和 $A(T_2)$ 的 Hhp - 双模拟。证明思路是展示每个 $T_1$ 和 $T_2$ 的多米诺双模拟能产生 $A(T_1)$ 和 $A(T_2)$ 的 Hhp - 双模拟，反之亦然。 - 对于 $A(T_i)$（$i \in \{1, 2\}$）的一次运行，由若干 $x_j$ 和 $y_k$ 事件的出现（分别为 $x$ 和 $y$ 次）以及最多两个 “$d$” 和 “$\hat{d}$” 事件组成。可将 $A(T_i)$ 的运行映射为三元组 $(F_i, x, y)$，其中 $F_i \subseteq E_{A(T_i)}$ 最多包含两个 “$d$” 和 “$\hat{d}$” 事件，$x, y \in \mathbb{N}$。 - 定义 $Confs(A(T_1), A(T_2))$ 为四元组 $(F_1, F_2, x, y)$ 的集合。存在 $A(T_1)$ 和 $A(T_2)$ 之间的 Hhp - 双模拟，当且仅当存在关系 $B \subseteq Confs(A(T_1), A(T_2))$，使得 $\{(e_1, e_2) : (F_1, F_2, x, y) \in B$，其中 $e_i$ 映射到 $(F_i, x, y)\}$ 是关联 $A(T_1)$ 和 $A(T_2)$ 的 Hhp - 双模拟。 - 以下两个断言直接推出命题 12： - 若 $B \subseteq Confs(A(T_1), A(T_2))$ 是关联 $A(T_1)$ 和 $A(T_2)$ 的 Hhp - 双模拟，则集合 $\{(d, e, x, y) : (\{d_{xy}\}, \{e_{xy}\}, x, y) \in B\}$ 是 $T_1$ 和 $T_2$ 的多米诺双模拟。 - 若 $B \subseteq Confs(T_1, T_2)$ 是关联 $T_1$ 和 $T_2$ 的多米诺双模拟，则集合 $\{(\{d_{xy}\}, \{e_{xy}\}, x, y) : (d, e, x, y) \in B\}$ 可扩展为 $A(T_1)$ 和 $A(T_2)$ 的 Hhp - 双模拟。 - **推论 14**：对于有限标记的 1 - 安全 Petri 网，Hhp - 双模拟是不可判定的。虽然描述的异步转换系统 $A(T)$ 不连贯，但通过闭合所有钻石（在 $(i, j \oplus 1)$ 位置用事件 $d_{ij}$ 和 $x_i$，在 $(i \oplus 1, j)$ 位置用事件 $\hat{d}_{ij}$ 和 $y_j$，$i, j \in \{0, \ldots, 3\}$）可使其接近连贯，且不影响命题 12 的证明。可以构造一个 1 - 安全 Petri 网，其派生的异步转换系统与上述 $A(T)$ 的完成形式同构。 以下是异步转换系统 $A(T)$ 部分关系的表格总结： |关系类型|具体关系| | ---- | ---- | |事件集合关系|$E_{A(T)} = \{x_i, y_i : i \in \{0, 1, 2, 3\}\} \cup