弱无环自动机与指数时间假设:完备性及相关问题
《Theoretical Computer Science》:Weakly Acyclic Automata and Exponential Time Hypotheses: Universality and Related Problems
【字体:
大
中
小
】
时间:2026年09月24日
来源:Theoretical Computer Science 1.1
编辑推荐:
摘要
弱无环非确定性有限自动机(NFA)是指其转移图中唯一的环是自环。NFAs 的通用性是 PSpace-完全的,除非 PSPACE=P,否则排除了多项式时间算法的可能性。这引发了一个问题:是否存在更快的,特别是亚指数时间算法?我们证明,即使对于弱无环 NFAs 的高度受限
摘要
弱无环非确定性有限自动机(NFA)是指其转移图中唯一的环是自环。NFAs 的通用性是 PSpace-完全的,除非 PSPACE=P,否则排除了多项式时间算法的可能性。这引发了一个问题:是否存在更快的,特别是亚指数时间算法?我们证明,即使对于弱无环 NFAs 的高度受限子类,在指数时间假设(ETH)下,通用性也不存在运行时间为 2^o(n) 的算法,即使是在二元字母表上;并且在强指数时间假设(SETH)下,对于随输入增长的字母表,也不存在运行时间为 O*(2^(n/(2+?))) 的算法(对任意 ? > 0)。这两个界限都与已知的一般 NFAs 的下界相匹配。我们进一步为相关问题建立了类似的下界,包括语言包含和等价性、长度受限的通用性,以及最短未被接受字符串问题。我们的结果表明,这些问题的指数复杂度是固有的,并非由非平凡环的存在所导致。
引言
语言包含、等价性和通用性是自动机理论中的基本问题,在计算机科学各领域都有应用。对于非确定性有限自动机(NFAs),这些问题是 PSpace-完全的 [1]。假设 PSPACE≠P,一个自然的问题是这些问题是否允许更高效的,特别是亚指数时间的算法。虽然各种技术改进了算法的实际运行时间 [2], [3], [4], [5], [6], [7],但其核心依赖于 NFA 确定化,这导致了指数级的最坏情况复杂度。事实上,确定化问题是 ExpTime-难的 [8],而判断子集构造是否导致状态数指数级膨胀本身就是 PSpace-难的 [9]。这些问题缺乏亚指数时间算法的情况已通过条件性下界得到形式化。Fernau 和 Krebs [10] 证明,在指数时间假设(ETH)下,不存在能在时间 2^o(n) 内判定 n 个状态 NFA 的通用性的算法。后来,这一结果在强指数时间假设(SETH)下得到加强,排除了运行时间为 O*(2^(n/(2+?))) 的算法(对任意 ? > 0)[11]。Oliveira 和 Wehar [12] 在 NC-SETH 下分析了 DFA 交集非空问题,这对 DFA 并集通用性问题隐含了更强的结果。
在本文中,我们重新审视弱无环 NFAs 及其变体的这些问题。如果自动机的转移关系在状态上诱导出偏序,即其转移图中唯一的环是自环,则称该自动机是弱无环的(或部分有序的,poNFA)。如果 poNFA 在自环转移和非自环转移之间没有非确定性选择,则称其为自环确定性的(rpoNFA,即受限 poNFA)。自环确定性的弱无环自动机在多种场景中自然出现。它们在弱无环图(WADs)中扮演关键角色,WADs 将 OBDDs 推广到表示无限语言 [13];在 XML 模式语言中,它们的语言可由确定性(一次无歧义)正则表达式定义 [14];在正则模型检验中,用于建模和验证分布式系统的性质 [15];在语言分离问题中 [16], [17];以及在离散事件系统中,作为验证用的简单无死锁模型 [18]。
Brzozowski 和 Fich [19] 研究了部分有序的 DFA(poDFAs),并证明它们刻画了 R-平凡语言。将该概念推广到 NFAs,Schwentick、Thérien 和 Vollmer [20] 证明了 poNFAs 刻画了 Straubing-Thérien 层次结构的 3/2 级 [21], [22],这是一个无限的星自由语言层次结构,与点深度层次 [23], [24], [25]、一阶逻辑 [26] 和复杂性理论 [27] 有关联。poNFAs 的语言也称为字母表模式约束(APC),即有效地在排列重写下封闭的正则语言 [15]。因此,poNFAs 严格比 poDFAs 具有更强的表达能力,而 poDFAs 的自然非确定性对应物由自环确定性的 poNFAs(rpoNFAs)给出 [14]。
Straubing-Thérien 层次结构的 1 级已知为分段可测试语言,由 Simon [28] 引入。这些语言由 J-平凡语法幺半群和可归一的 poDFAs 所刻画。对应的非确定性模型由完备且可归一的 rpoNFAs 给出,也称为 ptNFAs [29]。
尽管具有受限结构,判定 poNFAs 及上述变体的通用性仍然是 PSpace-完全的。对于 poNFAs,即使在二元字母表上该结果也成立。然而,对于固定字母表上的 rpoNFAs 和 ptNFAs,该问题降为 coNP-完全的 [14], [29]。
由于通用性是语言包含和等价性(与 Σ* 比较)的特例,这些复杂度界限同样适用于包含和等价性问题 [29]。
本文的主要结果是:通用性的指数复杂度在强结构限制下依然存在——弱无环 NFAs 在标准复杂性假设下不允许亚指数时间算法。
技术上的贡献包括两个在状态数上线性开销的规约,以及我们从中推导出的推论。规约是纯组合的,它们隐含的下界以 ETH 或 SETH 为条件。表 1 总结了所获得的图景与先前已知结果的关系。
除了通用性本身,贯穿全文还有两个细化版本,我们在此介绍它们。
首先,我们特别关注所有状态都是接受状态的自动机。对于一般 NFAs,在该限制下通用性仍然是 PSpace-完全的 [30];然而,已知的规约引入了非平凡环,因此不适用于弱无环设置。下面建立的所有下界对于所有状态都是接受状态的自动机都成立,这使其在该方面尽可能强。
其次,遵循 Gawrychowski 等人 [31],我们考虑通用性的两个长度受限变体。给定字母表 Σ 上的自动机 A 和以二进制编码的整数 ?,指定长度通用性询问 Σ^? ? L(A) 是否成立,有界长度通用性询问 Σ^≤? ? L(A) 是否成立。后者与确定最短未被接受字符串长度的问题密切相关:一个整数 ? 是语言 L 的最短未被接受字符串的长度当且仅当 ? 是使得 Σ^≤??1 ? L 成立的最大数。一个对偶问题,询问给定自动机是否接受某个给定长度的字符串,可以在时间 O(n^ω(log n)^{1+? log ?}) 内解决,其中 ω 是矩阵乘法的指数 [32]。
主要结果
• 从具有 n 个顶点和 m 条边的图上的 3-着色问题出发,我们在 O(n+m) 时间内构造一个具有 4n?2 个状态的 rpoNFA(所有状态都是接受状态)和一个具有 5n?3 个状态的 ptNFA,两者都在三字母字母表上,当且仅当图不存在适当的 3-着色时它们是通用的(命题 4)。字母表的二进制编码保持了线性状态数。ptNFA 还接受所有长度与 n 不同的字符串,这使得长度受限变体得以实现(推论 9)。
• 从具有 n 个变量和 m 个子句的 k-CNF 公式出发,我们在多项式时间内构造一个具有 2n+1 个状态的 rpoNFA(所有状态都是接受状态),在大小为 (n+1)^m 的字母表上,当且仅当公式可满足时它是通用的(命题 18)。如果公式不可满足,则自动机未接受的最短字符串长度为 2n。
第二个规约依赖于一个独立有意义的构造:一个具有 2n+1 个状态的 rpoNFA,其配置在 Zimin 字符串的驱动下按递增顺序枚举所有 2^n 个二进制计数器值(第 4.1 节)。
对指数困难性的推论
• 除非 ETH 不成立,否则 n 个状态的 ptNFAs 的通用性,以及所有状态都是接受状态的 n 个状态的 rpoNFAs 的通用性,不能在时间 2^o(n) 内判定,即使在二元字母表上也是如此(定理 5)。因此,相同的下界也适用于 poNFAs 和 NFAs。
• 除非 SETH 不成立,否则所有状态都是接受状态的 n 个状态的 rpoNFAs 的通用性不能在时间 O*(2^(n/(2+?))) 内判定(对任意 ? > 0)(定理 19)。此处字母表随输入增长;见注 20。
• 两个界限都延伸到语言包含和等价性(推论 6 和 21)、指定长度和有界长度通用性(推论 9 和 22),以及在 SETH 下确定最短未被接受字符串的长度(推论 23)。
复杂性结果
• 要求所有状态都是接受状态并不改变弱无环自动机通用性的复杂度:对于 poNFAs 和 rpoNFAs,受限问题的复杂度与无限制问题的复杂度相同(定理 24)。
• 指定长度和有界长度通用性对于二元字母表上的弱无环 NFAs 是 PSpace-完全的,对于字母表增长的 rpoNFAs 和 ptNFAs 也是 PSpace-完全的(引理 7)。对于固定字母表,两个问题的复杂度对于 rpoNFAs 和 ptNFAs 降为 coNP-完全的(引理 8)。
对描述复杂性的推论
• 存在所有状态都是接受状态的 n 个状态的 rpoNFAs,其最短未被接受字符串的长度为 2^(n?1)/2。
与先前工作的关系
虽然 Fernau 和 Krebs [10] 基于 ETH 的下界已经适用于弱无环 NFAs,但其他现有界限不适用。特别是,Oliveira 和 Wehar [12] 基于 Kozen 对 DFA-并集通用性的 PSpace-难证明 [33] 的结果,依赖于构造中至关重要的非平凡环;如果所有环都限制为自环,问题变得更简单且已知是 coNP-完全的 [29]。本文建立在 [11] 的结果之上,对其进行了大幅修订和扩展。特别是,所有关于通用性的结果也适用于其中研究的透明性概念。
考虑描述复杂性的结果,此前最好的界限由 Masopust 和 Kr?tzsch [29] 给出,他们构造了对于所有 k, n ≥ 1,在 n 字母字母表上具有 n(2k+1)+1 个状态的 ptNFA,其唯一未被接受的字符串长度为 (k+?? ??)?1;对于给定的状态数 N,该量在 k=n 时取最大值,此时为 2^Θ(N)。由于 ptNFAs 是完备且可归一的 rpoNFAs,相同的界限对 rpoNFAs 也成立,后者也直接获得了该结果 [14]。对于五字母字母表上的弱无环 NFAs,Ellul 等人 [34] 获得了 2^(n/25),二进制编码后破坏弱无环性后为 2^(n/75),后者在所有状态都是接受状态的情况下也成立 [30]。我们的构造将指数从 Θ(n) 提高到 Θ(n),代价是字母表随输入增长以及较弱的组合性质:[29] 的自动机拒绝单个字符串,而我们的自动机拒绝无限多个字符串。
各节摘要
预备知识
我们假定熟悉自动机理论 [35]。对于集合 S,其基数用 |S| 表示,其幂集用 2^S 表示。如果 S={x} 是单元素集,我们通常写 x 代替 {x}。字母表 Σ 是字母的有限非空集合。Σ 上的字符串是 Σ 中字母的有限序列。Σ 上所有字符串的集合用 Σ* 表示;空字符串用 ε 表示。Σ 上的语言是 Σ* 的子集。对于字符串 u ∈ Σ*,其长度用 |u| 表示。我们用 Σ^? 表示……
在指数时间假设下的困难性
我们回顾经典的 3-着色问题。无向图 G=(V,E) 的 3-着色是映射 μ: V → {a, b, c}。如果对于每条边 {u, v} ∈ E,μ(u) ≠ μ(v),则称该着色是适当的。问题询问给定图是否存在适当的 3-着色。
定理 1 [10], [39]:除非 ETH 不成立,否则 n 个顶点和 m 条边的图上的 3-着色问题不能在时间 2^o(n+m) 内解决。
Fernau 和 Krebs [10] 展示了如何将 n 个顶点和 m 条边的图上的 3-着色问题规约到具有 Θ(n+m) 个状态的 NFA 的通用性问题……
在强指数时间假设下的困难性
我们现在在强指数时间假设(SETH)下加强先前的结果,证明 rpoNFAs 的通用性不能用比穷举搜索显著更快的算法判定。证明分为两步。首先,我们构造一个 rpoNFA A_n,其配置模拟从 0 到 2^n?1 的二进制计数器。计数器值编码在当前配置中,即在 A_n 的活动状态子集中。此外,该自动机接受所有字符串,除了那些具有……
所有状态都是接受状态的自动机
Kao 等人 [30] 研究了所有状态都是接受状态的 NFAs,并证明对于这样的 NFAs,判定通用性是 PSpace-完全的。然而,他们的规约引入了环,因此不适用于弱无环 NFAs。为了完整性,我们证明要求所有状态都是接受状态并不影响弱无环 NFAs 及其自环确定性子类 rpoNFAs 的通用性复杂度。这一观察不适用于 ptNFAs:由于其完备性……
结论
我们研究了弱无环 NFAs 若干类的通用性问题的条件性下界。我们证明,假设 ETH 成立,对于所考虑的任何一个自动机类,都不存在时间复杂度为 2^o(n) 的亚指数时间算法来判定通用性,即使在二元字母表上也是如此。
在SETH(扩展强指数时间假设)下,我们通过证明对于任何c > 2,都不存在能在O*(2^n/c)时间内判定rpoNFA通用性的算法,进一步加强了这一结果;即使自动机的所有状态都是接受状态,这一结论仍然成立。
CRediT作者贡献声明
Ji?í Balun:研究调查。
Tomá? Masopust:研究调查。
Petr Osi?ka:研究调查。
利益冲突声明
作者声明他们没有已知的竞争性财务利益或个人关系可能对本论文中报告的工作产生影响。
Ji?í Balun | Tomá? Masopust | Petr Osi?ka
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号