《非均匀元胞自动机与保守广群的语言识别研究》

### 《非均匀元胞自动机与保守广群的语言识别研究》 在计算机科学和数学领域，元胞自动机和广群的研究一直是重要的课题。元胞自动机在模拟复杂系统和动态过程中有着广泛的应用，而广群作为一种代数结构，其语言识别能力也备受关注。本文将深入探讨非均匀元胞自动机（ν - CA）的复杂度类以及保守广群的语言识别特性。 #### 1. 非均匀元胞自动机的复杂度类 非均匀元胞自动机（ν - CA）涉及到局部规则分布的语言复杂度问题。研究表明，对于半径为 1 的线性 ν - CA，与等连续或敏感 ν - CA 分布相关的语言是 ζ - 有理的。然而，将这一结果扩展到更高半径的局部规则分布集合是一项具有挑战性的任务，因为这会归结为在非交换环上研究半径为 1 的 ν - CA 的等连续性，从而失去一些如命题 21 这样“方便”的结果。 此外，在 ν - CA 中，给出单射 ν - CA 的分布集合与敏感（加上之前提到的约束）的分布集合之间不存在复杂度差距。这与直觉相悖，因为单射性是全局转移函数的性质，而敏感性是其迭代的性质。研究人员怀疑，给出单射 ν - CA 的分布的特征可以加强为确定性 ζ - 有理语言。 还有一个值得研究的方向是，探索与复杂度高于 ζ - 有理的语言相关的 ν - CA 的动态特性。研究人员认为，对初始条件的敏感性（无进一步约束）是一个很好的候选特性。另外，还可以从 ν - CA 领域发散出去，研究有限自动机的快速失败接受条件所给出的语言的拓扑结构。 #### 2. 保守广群的语言识别 广群是配备二元运算“·”的集合，该运算不一定满足结合律。有限半群对语言的识别概念可以推广到有限广群。已知一个语言可以被广群识别当且仅当它是上下文无关的，但某些广群子类只能识别正则语言。 保守广群是指对于所有的 a, b 属于广群 H，都有 a · b 属于 {a, b}。本文的主要结果是保守广群只能识别正则语言。这个类与 Beaudry 等人所描述的类不可比，因此展示了广群在无法具有上下文无关能力方面的一种新情况。 ##### 2.1 保守广群与锦标赛 可以将保守广群看作是石头 - 剪刀 - 布游戏的推广。对于任何保守广群 H，定义一个游戏，玩家 1 和玩家 2 分别选择 H 中的一个元素（设为 a 和 b），玩家 1 获胜当且仅当 a · b = a。 考虑广群元素的序列 w ∈ H*，对这个序列进行括号化可以看作是指定一个涉及 w 中符号的锦标赛结构，即确定 w 中元素获胜者的一种特定方式。例如，如果 w = abcd，那么 (a · b) · (c · d) 表示先让 a 与 b 比赛，c 与 d 比赛，然后让这两轮的获胜者进行比赛。 为了研究语言 Λ(x) = {w ∈ H* | w 可以被括号化以得到 x}，定义了竞赛树。设 T 是所有竞赛树的集合，它是满足以下条件的最小集