💻 computer science

The complexity of downward closures of indexed languages

本文通过一种新颖的方法，利用基于半群的词摘要将索引文法转化为上下文无关文法，分别对非确定性和确定性自动机建立了三重和四重指数级上界，并给出了匹配的下界，从而解决了关于计算索引语言向下闭包复杂性的开放性问题。

原作者： Richard Mandel, Corto Mascle, Georg Zetzsche

发布于 2026-05-28

📖 1 分钟阅读☕ 轻松阅读

原作者： Richard Mandel, Corto Mascle, Georg Zetzsche

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你拥有一个庞大且无限复杂的图书馆，里面收藏着无数故事。有些故事很短，有些长达数百万页，还有些遵循着极其复杂的规则，以至于普通计算机甚至无法读取它们。在计算机科学领域，这些故事被称为索引语言（Indexed Languages）。它们就像是标准“上下文无关语言”（Context-Free Languages，即支撑编程语言语法的语言）的超级增强版，但多出了一层复杂性：“栈的栈”。

把普通栈想象成一摞盘子。你可以加一个盘子，也可以拿走一个盘子。而索引语言则像是拥有了一摞“整塔的盘子”。你可以添加一整座塔，或者拿走一整座塔。这使得该系统极其强大，但也极难分析。

问题：“向下闭包”

本文的作者们关注一种简化这些庞大图书馆的具体方法。他们称之为向下闭包（Downward Closure）。

想象你有一个非常长的句子：“那只敏捷的棕色狐狸跳过了那只懒惰的狗。”
这个句子的“向下闭包”是指通过删除字母（但保持顺序）所能构成的所有可能更短的句子的集合。

“狐狸跳”在闭包中。
“敏捷狗”在闭包中。
“狗敏捷”不在闭包中（因为顺序改变了）。

我们为什么关心这个？因为原始图书馆可能是无限的且无法处理的。但“向下闭包”（所有可能子故事的集合）始终是正则的（Regular）。用计算机术语来说，这意味着它可以由一个简单的有限机器（如基本流程图）来描述。这是一种将混乱、无限的一团糟转化为整洁、可管理的模式列表的方法。

核心问题： 我们已知可以将这些复杂的索引语言转化为简单的列表（向下闭包）。但我们不知道这个列表会有多大。它会像电话簿那么大吗？像整个互联网那么大？还是大到编写它所需的时间超过宇宙年龄？

发现：三重指数爆炸

作者曼德尔（Mandel）、马斯克莱（Mascle）和泽策施（Zetzsche）最终解开了这个谜团。他们证明，将一个索引语言转化为其简单的向下闭包，所得到的机器规模可能是**三重指数级（triply exponential）**的。

让我们用一个比喻来拆解“三重指数”的含义：

线性： 如果你有 10 个物品，你需要 10 个盒子。
指数级： 如果你有 10 个物品，你需要 $2^{10}$ （1,024）个盒子。
双重指数级： 如果你有 10 个物品，你需要 $2^{2^{10}}$ （超过一百万亿）个盒子。
三重指数级： 如果你有 10 个物品，你需要 $2^{2^{2^{10}}}$ 个盒子。这个数字如此巨大，几乎无法理解。这就像试图数清地球上每个海滩上的每一粒沙子，然后对地球上每个海滩上的每一粒沙子都重复这个过程……

作者们表明，对于索引语言而言，“向下闭包”机器的规模大致就是如此巨大。他们还证明，你无法做得更好；对于某些语言，机器必须这么大。

他们是如何做到的：“摘要”技巧

如何将一摞塔压缩成一个简单的列表，同时不丢失识别模式的能力？

作者们使用了来自数学分支**半群理论（Semigroup Theory）**的一个巧妙技巧。想象你在阅读一个很长的故事，但你只关心故事的“氛围”，而不是每一个字。

如果一个故事反复出现特定的模式（就像歌曲中的副歌），你不需要每次都写下整个副歌。你只需写下“副歌”然后继续。
作者们为这些栈创建了一个数学“摘要”。他们不再追踪栈中的每一个“盘子”或“塔”，而是用单个摘要符号替换长序列的相同模式。

他们证明，尽管这些栈是无限的，但可以用这些摘要来替换它们。一旦这样做，复杂的“索引文法”就变成了更简单的“上下文无关文法”（一种标准的计算机文法）。然后，他们利用现有方法将该简化文法转化为最终的向下闭包机器。

结果：新纪录

在这篇论文之前，人们知道这个问题是可解的，但不知道代价有多大。

上界： 他们构建了一种生成机器的方法，这需要三重指数级的时间和空间。
下界： 他们还构建了一个特定的、棘手的语言，该语言迫使任何机器至少达到三重指数级的规模。

这意味着他们找到了这个问题的确切“价格标签”。这不仅仅是“困难”，而是“三重指数级困难”。

他们还将此应用于另外两个问题：

比较： 如果你有两个复杂的语言，你能判断它们的“向下闭包”是否相同吗？答案是肯定的，但这是一个**co-3-NEXP 完全（co-3-NEXP-complete）**问题。用通俗的话说：这是一个极其难以解决的谜题，处于计算机在合理时间范围内理论上能够处理的边缘。
泵引阈值： 他们证明，在有限索引语言中，在开始重复模式之前能生成的最长单词的长度也是三重指数级的。

总结

将索引语言想象成一个巨大的、无限的迷宫。“向下闭包”就是穿过该迷宫所有可能捷径的地图。

旧知识： 我们知道地图存在。
新知识： 我们现在知道，对于最复杂的迷宫，地图是如此巨大，以至于计算机绘制它所需的时间超过了宇宙的年龄。
方法： 作者们找到了一种通过总结重复部分来缩小迷宫规模的方法，使他们能够绘制地图并证明其必须有多大。

他们不仅仅是猜测；他们构建了地图，并证明了没有任何更小的地图可能奏效。

技术摘要：索引语言向下闭包的复杂性

问题陈述

本文探讨了构建索引语言向下闭包的计算复杂性。语言 $L$ 的向下闭包，记为 $L^\downarrow$ ，是 $L$ 中所有单词的散乱子词（scattered subwords）的集合。根据希格曼引理（Higman's Lemma）， $L^\downarrow$ 始终是一个正则语言，使其成为无限状态系统验证（例如高阶模型检测、异步程序和丢包信道系统）中至关重要的正则过近似工具。

尽管索引语言（等价于二阶下推自动机或 2-PDA）向下闭包的可计算性已于 2015 年通过基于良拟序的通用算法得以确立，但该构造的复杂度界限仍是一个未解问题。具体而言，此前尚不清楚是否存在原始递归构造，且对于所得自动机的大小，既无已知上界也无下界。在此项工作之前，索引语言向下闭包的非确定性有限自动机（NFA）大小的最佳已知下界是双指数的，而向下闭包包含性和等价性等判定问题的复杂度已知至少为 co-2-NEXP 难。

方法论

作者通过提供紧确的（渐近匹配的）上下界解决了这一未解问题。他们的方法依赖于对栈内容的一种新颖代数抽象，旨在将索引文法转换为上下文无关文法（CFG），同时保持向下闭包不变。

1. 产生性与标注

该构造始于确保输入索引文法是产生性的（即每个句型都能推导出终结符单词）。作者引入了一种标注版本的文法，其中栈符号与能从该栈配置推导出终结符单词的非终结符集合配对。这防止了生成无法对语言做出贡献的“死”项，这一性质对于在后续转换中保持向下闭包至关重要。

2. 栈幺半群与摘要

核心技术创新涉及有限半群理论。作者定义了一个栈幺半群 $M$ （一个由布尔矩阵组成的有限幺半群），用于编码相对于文法非终结符的栈操作（压入和弹出）行为。

摘要：他们利用半群理论的最新进展（特别是 Jecker 和 Gimbert 等人的成果）来计算任意长栈单词的摘要。摘要是对栈单词的压缩表示，保留了足够的信息，以便确定相对于幺半群 $M$ 的压入/弹出操作的结果。
泵送与跳过：作者引入了两条新的推导规则，即泵送（pump）和跳过（skip），允许扩展和缩减映射到幺半群中同一幂等元素的栈中缀。他们证明了这些规则不会改变语言的向下闭包。
压缩：通过应用这些规则，他们表明任何栈内容都可以被压缩为大小有界的摘要（相对于文法大小呈指数级）。这种压缩有效地丢失了关于确切栈内容的信息，但保留了向下闭包。

3. 归约至上下文无关文法

利用这些摘要，作者构建了一个上下文无关文法（CFG） $G_{CFG}$ 来模拟原始索引文法 $G$ 。在 $G_{CFG}$ 中，索引文法的栈内容被其摘要所取代。

$G_{CFG}$ 的非终结符是三元组 $(A, X, \sigma)$ ，其中 $A$ 是非终结符， $X$ 是非终结符集合， $\sigma$ 是可行的摘要。
原始文法中的压入和弹出操作通过摘要上的操作（使用在幺半群上定义的 push 和 pop 关系）来模拟。
作者证明了 $L(G_{CFG})^\downarrow = L(G)^\downarrow$ 。

4. 复杂度分析

由于摘要的大小相对于文法大小呈指数级有界，生成的 CFG $G_{CFG}$ 具有双指数大小。现有的计算 CFG 向下闭包的算法会产生一个相对于 CFG 呈指数级大小的 NFA。因此，组合后的结果产生了一个大小为三指数的 $L(G)^\downarrow$ 的 NFA。

对于确定性有限自动机（DFA），应用于该三指数 NFA 的标准子集构造法导致了四指数的上界。

主要贡献与结果

上界

NFA 大小：给定大小为 $n$ 的索引文法，可以在三指数时间内计算其向下闭包的 NFA，且其大小至多为三指数（ $O(\exp_3(n))$ ）。
DFA 大小：可以构建一个大小至多为四指数（ $O(\exp_4(n))$ ）的 DFA 来表示其向下闭包。
判定问题：索引语言的向下闭包包含性（ $L_1^\downarrow \subseteq L_2^\downarrow$ ）和等价性（ $L_1^\downarrow = L_2^\downarrow$ ）问题是co-3-NEXP 完全的。

下界

作者提供了匹配的下界，证明了其上界的紧确性：

NFA 下界：存在一族多项式大小的索引文法，使得其向下闭包的任意 NFA 至少需要三指数个状态。这是通过构建生成语言 $\{a^{\exp_3(n)}\}$ 的文法实现的。
DFA 下界：存在一族索引文法，使得其向下闭包的任意 DFA 至少需要四指数个状态。
泵送阈值：结果表明，索引文法的泵送阈值（大小为 $n$ 的有限索引语言中单词的最大长度）至少呈三指数级增长，修正了文献中此前关于双指数界限的断言。

意义

本文解决了一个关于索引语言向下闭包复杂性的长期未解问题。

紧确界限：它确立了其复杂度严格高于上下文无关语言（后者对于 NFA 是双指数的），但低于通常与 $k > 2$ 阶高阶系统相关的通用指数塔。鉴于其他问题（如空性问题）的复杂度随下推自动机的阶数呈线性增长，索引语言（二阶）从双指数到三指数的跳跃是出乎意料的。
算法可行性：它证实了存在原始递归构造，解决了该问题仅仅是可计算的还是在特定复杂度类内可有效构造的问题。
方法论进展：利用基于半群的摘要来压缩栈内容同时保持向下闭包的技术，为分析高阶系统提供了一种新工具，可能适用于更广泛的无限状态系统类别。

作者强调，他们的结果源于将索引文法到 CFG 的构造性转换，利用栈幺半群的代数性质以保留对向下闭包至关重要的子词结构的方式，来管理栈的无界性。