1. 论文基本信息

1.1. 标题

Ambiguity, Nondeterminism and State Complexity of Finite Automata (有限自动机的歧义性、非确定性与状态复杂度)

1.2. 作者

• Yo-Sub Han
• Arto Salomaa
• Kai Salomaa

1.3. 发表期刊/会议

未明确指明发表期刊或会议，但从文章布局和致谢部分来看，这通常是期刊文章、会议论文集中的一篇或特邀综述。根据链接中的 actacyb_amb_sc.pdf 推测，可能与 Acta Cybernetica 相关，这是一本在理论计算机科学领域具有一定声誉的期刊。

1.4. 发表年份

文章中未明确给出发表年份，但参考文献列表显示，最新的引用文献为 2016 年（如 [22] Jirasek et al. 2016），且致谢部分提到“Yonsei University Future-leading Research Initiative of 2016”，因此推断该文章可能发表于 2016 年末或 2017 年初。

1.5. 摘要

这篇论文综述了有限自动机 (Finite Automata, FA) 中歧义度 (degree of ambiguity) 和各种非确定性 (nondeterminism) 度量方法的研究工作。歧义度衡量的是一个非确定性有限自动机 (Nondeterministic Finite Automaton, NFA) 对于给定输入所接受的计算路径数量。非确定性则可以通过计算过程中猜测的量（如单个计算中的猜测次数）或给定输入上计算树 (computation tree) 的叶子数量来衡量。论文特别关注具有量化歧义性或非确定性的 NFA 之间的状态复杂度 (state complexity) 比较。

1.6. 原文链接

https://toc.yonsei.ac.kr/~emmous/papers/actacyb_amb_sc.pdf 该链接指向论文的 PDF 文件，其发布状态推测为已正式发表或预印本。

2. 整体概括

2.1. 研究背景与动机

研究背景: 有限自动机 (FA) 自 20 世纪 50 年代以来一直是计算理论的基础模型，尽管已有大量研究，但仍存在许多未解决的问题。其中一个重要的研究方向是描述复杂性 (descriptional complexity)，或称状态复杂性 (state complexity)，它关注识别特定语言所需的最小自动机大小。状态复杂性衡量的是一个正则表达式语言所需的确定性有限自动机 (Deterministic Finite Automaton, DFA) 或非确定性有限自动机 (NFA) 的最优状态数量。

核心问题与动机: 论文试图解决的核心问题是：

1. 如何量化 NFA 的歧义性与非确定性？ 传统的 NFA 概念只区分确定性与非确定性，但并未细致衡量非确定性的“程度”。歧义性 (ambiguity) 衡量接受计算的数量，而非确定性 (nondeterminism) 则通过计算中的“猜测”量或计算树的叶子数来量化。
2. 不同量化程度的歧义性或非确定性对 NFA 的状态复杂性有何影响？ 也就是说，如果一个 NFA 允许更高程度的歧义或非确定性，它是否能够用更少的 states 来识别相同的语言？反之，如果限制了歧义或非确定性，状态数量会如何增加？
3. 不同非确定性度量之间的关系是什么？ 例如，歧义度与计算树宽度、猜测量之间是否存在某种内在联系？

重要性与挑战: 这些问题在理论计算机科学中至关重要，因为它们深入探讨了非确定性的计算能力及其对描述复杂性的影响。现有研究表明，即使是明确定义的非确定性，其量化方式也多种多样，且不同量化方式对自动机大小的影响差异显著。例如，将 NFA 转换为 DFA 可能会导致状态数量呈指数级增长，而歧义性或非确定性的定量限制可能改变这种增长的界限。理解这些关系有助于设计更高效的算法、构建更简洁的模型，并深入理解计算的本质。

切入点与创新思路: 这篇论文的切入点是一项综述性工作 (survey work)。它并非提出新的理论或算法，而是系统地回顾和总结了现有关于 NFA 歧义度增长率、各种非确定性度量、以及这些度量与状态复杂性比较方面的研究。其创新之处在于，它将散落在各处的、关于不同量化非确定性或歧义性的工作进行了整合、分类和比较，特别关注了它们在状态复杂性上的权衡，并指出了该领域的开放问题和未来研究方向，为初学者和资深研究人员提供了一个全面的视角。

2.2. 核心贡献/主要发现

这篇综述论文的核心贡献在于对有限自动机中歧义性与非确定性度量及其状态复杂性比较研究进行了全面的梳理和总结，具体体现在以下几个主要发现：

1. 明确了歧义性与非确定性的多种量化方法： 论文详细定义了 NFA 的歧义度 (degree of ambiguity)，并将其分为有限歧义 (finitely ambiguous, FNFA)、多项式歧义 (polynomially ambiguous, PNFA) 和指数歧义 (exponentially ambiguous) 等类别。同时，它还介绍了多种非确定性度量，包括计算的 猜测 (guessing) 量、分支 (branching) 数、跟踪 (trace) 以及 计算树宽度 (tree width)，并对它们的增长率进行了分类（有界、多项式、指数）。

2. 揭示了不同歧义级别 NFA 的状态复杂性分离：

   • UFA 到 DFA 的指数级膨胀： 明确指出，将无歧义 NFA (Unambiguous NFA, UFA) 确定化 (determinization) 最坏情况下会导致状态数量的指数级增长 ($2^n - 1$)。
   • NFA 到 PNFA 的超多项式分离： 强调了普通 NFA (general NFA) 比多项式歧义 NFA (PNFA) 在简洁性上具有超多项式 (super-polynomially) 的优势，即存在 $n$ 状态 NFA，其等价的 PNFA 需要超多项式数量的状态。
   • PNFA 到 FNFA 的超多项式分离： 解决了长期开放的问题，证明了多项式歧义 NFA (PNFA) 比有限歧义 NFA (FNFA) 在简洁性上具有超多项式优势，即存在 $n$ 状态 PNFA，其等价的 FNFA 需要至少 $2^{\Omega(n^{1/3})}$ 状态。

3. 探讨了非确定性度量与状态复杂性的关系：

   • 有限分支 NFA 的“频谱结果”： 总结了 Goldstine et al. 的工作，表明对于一个固定语言，不同有限量的分支 (branching) 可以带来渐进的状态数量节省。存在一个“频谱”，展示了随着允许的分支数量增加，所需状态数如何从 $2^n$ 减少到 $n+1$。
   • 有限树宽度 NFA 到 DFA 的多项式转换： 指出具有有限树宽度的 NFA 可以转换为多项式大小的 DFA，这与一般 NFA 的指数级转换形成了对比。
   • NFA 到 MDFA 的转换： 综述了 NFA 到具有多个初始状态的 DFA (MDFA) 的高效模拟，并给出了匹配的下界。

4. 识别并强调了开放问题： 论文不仅总结了已知成果，还明确指出了该领域的几个关键开放问题，如：

   • 对于非有界 (unbounded) 非确定性度量（如分支或树宽度），其增长率是否必须是超多项式？

   • 当非确定性量（如分支或树宽度）是非有界且作为输入长度的函数时，NFA 的状态复杂性如何？这方面已知成果甚少。

   • 不同非确定性度量（如歧义度和分支/树宽度）之间的简洁性比较。

     通过这些总结和分析，该论文为理解 NFA 的非确定性及其对描述复杂性的深远影响提供了一个结构化的框架，并为未来的研究指明了方向。

3. 预备知识与相关工作

3.1. 基础概念

为了理解这篇论文，需要掌握以下核心概念：

• 有限自动机 (Finite Automaton, FA): 一种计算模型，用于识别形式语言。它由一组状态、一个输入字母表、一个转移函数、一个初始状态和一组接受状态组成。

  • 非确定性有限自动机 (Nondeterministic Finite Automaton, NFA):
    • 定义为一个五元组 $A = (Q, \Sigma, \delta, q_0, F)$。
    • $Q$ 是有限状态集合 (finite set of states)。
    • $\Sigma$ 是输入字母表 (input alphabet)。
    • $\delta: Q \times \Sigma \to 2^Q$ 是转移函数 (transition function)，对于一个状态和一个输入符号，可以转移到零个、一个或多个状态。这就是“非确定性”的来源。
    • $q_0 \in Q$ 是初始状态 (initial state)。
    • $F \subseteq Q$ 是接受状态集合 (set of final states)。
    • NFA 接受一个字符串 $w$ 如果存在至少一条从 $q_0$ 开始，读完 $w$ 后到达某个 $F$ 中状态的计算路径。
  • 确定性有限自动机 (Deterministic Finite Automaton, DFA):
    • 一种特殊的 NFA，其转移函数 $\delta: Q \times \Sigma \to Q$ 满足对任意状态 $q \in Q$ 和输入符号 $b \in \Sigma$，$\delta(q, b)$ 只有一个输出状态（或者没有输出状态，即不完整 DFA）。也就是说，对于任何给定输入，DFA 只有一条确定的计算路径。

• 正则表达式 (Regular Expressions): 一种用于描述正则表达式语言的符号序列。它们可以表示字符串模式，并与有限自动机等价。

• 正则语言 (Regular Languages): 能够被有限自动机识别的语言集合。

• 状态复杂性 (State Complexity):

  • 对于一个正则语言 $L$，其状态复杂性 (state complexity) 是识别 $L$ 的最小 DFA 的状态数量。
  • 其非确定性状态复杂性 (nondeterministic state complexity) 是识别 $L$ 的最小 NFA 的状态数量。
  • 描述复杂性 (descriptional complexity) 是一个更广泛的概念，关注描述计算模型（如自动机）所需资源的最小数量。

• 计算 (Computation):

  • NFA 在输入字符串 $w = b_1 b_2 \cdots b_k$ 上的一个计算是一个状态序列 $(p_1, \ldots, p_\ell)$。
  • 接受计算 (accepting computation): 一个完整的计算，从初始状态开始，读完整个输入字符串，并结束于一个接受状态 $F$ 中的状态。
  • 计算树 (computation tree): 表示 NFA 在给定输入上的所有可能计算路径的树状结构。树的叶子代表所有可能的计算结束点。

• 歧义度 (Degree of Ambiguity):

  • NFA $A$ 在字符串 $w$ 上的歧义度 $\mathrm{da}_A(w)$ 是 $A$ 在 $w$ 上接受计算的数量。
  • 无歧义 NFA (Unambiguous NFA, UFA): $\mathrm{da}_A(w) \leq 1$ 对于所有 $w \in \Sigma^*$。
  • 有限歧义 NFA (Finitely Ambiguous NFA, FNFA): $\mathrm{da}_A(m)$ (在长度为 $m$ 的字符串上的最大歧义度) 是有界的。
  • 多项式歧义 NFA (Polynomially Ambigous NFA, PNFA): $\mathrm{da}_A(m)$ 由一个多项式 p(m) 上界。
  • 指数歧义 NFA (Exponentially Ambigous NFA): $\mathrm{da}_A(m)$ 呈指数增长。

• 非确定性度量 (Nondeterminism Measures):

  • $\text{猜测} (Guessing,$\gamma_A(C)): 单个计算 $C$ 中“猜测”的量，通常以信息比特数衡量。对于一个转换 $\delta(q, b)$，如果 $| \delta(q, b) |$ 个状态可以选择，则猜测量为 $\log_2 | \delta(q, b) |$。
    • 对于一个计算 $C = (p_1, \ldots, p_\ell)$，其猜测量定义为： $$\gamma_A (C) = \log_2 { \left| \delta ( q_0 , b_1 ) \right| } + \sum_{i=1}^{\ell-1} \log_2 { \left| \delta ( p_i , b_{i+1} ) \right| }$$ 其中 $q_0$ 是初始状态，$\delta(q_0, b_1)$ 是第一个转换，$\delta(p_i, b_{i+1})$ 是后续转换。
  • $\text{分支} (Branching,$\beta_A(C)): 是猜测量的指数形式，$\beta_A(C) = 2^{\gamma_A(C)}$。直观上，它表示一个计算 $C$ 实际“选择了多少条”路径中的一条。
  • $\text{最大猜测} (Maximum Guessing,$\gamma_A^{\mathrm{max}}(w)): 在所有计算（不限于接受计算）中，对于字符串 $w$ 的最大猜测量。
  • $\text{跟踪} (Trace,$\tau_A(w)): $\tau_A(w) = 2^{\gamma_A^{\mathrm{max}}(w)}$。
  • $\text{计算树宽度} (Tree Width,$\mathrm{tw}_A(w)): NFA 在字符串 $w$ 上所有计算的总数量（即计算树的叶子数量）。

• 超多项式分离 (Super-polynomially separated):

  • 如果一类设备 $Y$ (例如 NFA) 能够用 $n$ 个状态识别一系列语言 $L_n$，但任何来自另一类设备 $X$ (例如 PNFA) 的等价设备都需要超过任意多项式 p(n) 的状态数量，那么称 $Y$ 类与 $X$ 类是超多项式分离的。这表明 $Y$ 类在简洁性上比 $X$ 类具有显著优势。

3.2. 前人工作

论文提及并构建在其基础上的关键先前研究包括：

• 自动机歧义性的早期研究：
  • Book et al. [3]: 首次系统性地研究了正则表达式和 NFA 的歧义性，以及它们之间的关系。他们定义了一个正则表达式是无歧义的，如果它以至多一种方式表示每个字符串；一个 NFA 是无歧义的，如果每个字符串至多有一个接受计算。
  • Brüggemann-Klein and Wood [4]: 引入了更严格的 1-unambiguity (1-无歧义性) 概念，即其位置自动机 (position automaton) 是确定性的。
• 状态复杂性与歧义性的权衡：
  • Ravikumar and Ibarra [42]: 系统地研究了无歧义 NFA (UFA)、有限歧义 NFA (FNFA)、多项式歧义 NFA (PNFA) 和指数歧义 NFA 之间的状态大小权衡。他们证明了对于有界语言 (bounded languages)，FNFA 和 UFA (以及 UFA 和 DFA) 之间存在超多项式分离。
  • Leung [30]: 建立了里程碑式的分离结果，证明了存在 $n$ 状态的指数歧义 NFA，其任何等价的多项式歧义 NFA 都需要 $2^n - 1$ 个状态，从而将一般 NFA 与 PNFA 进行了超多项式分离。
  • Hromkovi et al. [19, 20]: 利用通信复杂性 (communications complexity) 的强大技术，为不同歧义度 NFA 的状态复杂性分离提供了更简洁的证明，并进一步证明了 PNFA 与 FNFA 之间的超多项式分离。
• NFA 歧义度的可判定性与增长率：
  • Mandel and Simon [33], Reutenauer [43]: 独立证明了给定 NFA 是否是有限歧义或多项式歧义是可判定的，并提出了计算多项式增长度的算法。
  • Weber and Seidl [50]: 给出了有限歧义和多项式歧义 NFA 的更简单的结构性刻画，并提供了多项式时间算法，还给出了有限歧义 NFA 歧义度的上界。
• 非确定性量化方法：
  • Kintala and Fischer [25]: 首次在图灵机计算中考虑非确定性度量。
  • Kintala and Wotschke [26]: 首次量化了有限自动机计算中的非确定性，并指出不同有限非确定性选择数量的 NFA 在确定化大小膨胀上存在显著差异。
  • Goldstine et al. [11]: 提出了关于非确定性的“频谱结果”，表明不同有限量的分支能够带来渐进的状态数量节省。
  • Goldstine et al. [12], Hromkovi et al. [19]: 建立了歧义度与各种非确定性度量之间的关系。
  • Leung [31]: 研究了有限非确定性 NFA 的状态复杂性，并给出了有限猜测量的上界。
  • Palioudakis et al. [38, 39, 40, 41]: 深入研究了计算树宽度、最大猜测、跟踪等非确定性度量，以及它们之间的关系和状态复杂性。

3.3. 技术演进

该领域的技术演进大致遵循以下脉络：

1. 基础理论建立 (20世纪50-70年代): 从有限自动机和正则语言的基础定义开始，研究它们的基本性质、表达能力以及 DFA 和 NFA 之间的等价性。
2. 描述复杂性兴起 (20世纪70-80年代): 关注识别相同语言所需的自动机大小。Maslov [34] 和 Schmidt [46] 等人开始研究各种正则语言操作的状态复杂性，并发现 DFA 到 NFA 转换可能带来指数级状态节省。
3. 歧义性概念的引入与量化 (20世纪70-90年代): Book et al. [3] 首次系统性研究了歧义性。随后，研究者开始区分不同程度的歧义性（无歧义、有限歧义、多项式歧义、指数歧义），并探讨其可判定性问题。
4. 非确定性度量的细化与量化 (20世纪80-90年代): Kintala 和 Wotschke [26] 等人开始尝试量化 NFA 中的非确定性，而不仅仅是二元区分。引入了“猜测”、“分支”、“计算树宽度”等概念，以更精细地衡量非确定性。
5. 歧义度与非确定性度量对状态复杂性影响的研究 (20世纪80年代至今): 这一阶段是本综述的核心。研究聚焦于：
   • 不同歧义度 NFA 之间（如 NFA vs. PNFA vs. FNFA vs. UFA vs. DFA）的简洁性比较，并确立了多项式到超多项式的分离结果（Ravikumar and Ibarra [42], Leung [30], Hromkovi et al. [19, 20]）。
   • 不同非确定性度量（如有限分支、有限树宽度）下的 NFA 与 DFA 之间的状态复杂性关系，并产生了“频谱结果”和多项式转换界限（Goldstine et al. [11], Palioudakis et al. [38]）。
   • 研究各种度量之间的相互关系，例如歧义度与猜测量、计算树宽度之间的联系（Goldstine et al. [12]）。
6. 通信复杂性技术的应用 (21世纪初至今): Hromkovi et al. [19, 20] 引入通信复杂性技术，为状态复杂性分离提供了强大的证明工具，使得一些长期开放的问题得以解决。

3.4. 差异化分析

这篇论文本身是一篇综述，因此其“方法”主要是对现有研究进行分类、总结和比较，而不是提出新的算法或模型。它将该领域的研究分为两大主线：歧义性 (Ambiguity) 和 非确定性 (Nondeterminism)，并在这两条主线下探讨它们对 状态复杂性 (State Complexity) 的影响。

核心区别和创新点体现在以下几个方面：

• 分类与统一视角： 论文将多种不同的 NFA 量化特性（歧义度、猜测、分支、树宽度）整合在一个框架下进行讨论，提供了一个统一的视角来理解 NFA 的非确定性能力。

• 强调状态复杂性比较： 明确将重点放在了这些量化特性如何影响 NFA 的简洁性，即它们与等价 DFA 或不同限制条件下的 NFA 之间状态数量的权衡。这使得研究焦点从单纯的定义和可判定性转移到实际的描述效率。

• 揭示分离与谱系： 详细比较了各种 NFA 类（DFA、UFA、FNFA、PNFA、NFA）之间的简洁性差异，明确指出了哪些类别之间存在超多项式分离，哪些则有更精细的“频谱结果”。例如，从无歧义到有限歧义，再到多项式歧义和一般 NFA，描述复杂性呈现阶梯式增长。

• 梳理度量间关系： 探讨了不同非确定性度量（如歧义度、计算树宽度、猜测量）之间的内在联系和转换关系，例如树宽度与猜测量、歧义度之间的不等式关系。

• 指明开放问题： 作为一篇综述，其重要贡献在于清晰地识别并阐述了该领域尚未解决的关键问题，如对非有界非确定性度量的状态复杂性比较，以及通信复杂性技术在这些问题上的潜在应用，这为未来的研究提供了明确的指导。

  简而言之，本文的“差异化”在于其作为一篇全面的、聚焦于状态复杂性权衡的、且指明了未来方向的综述，将分散的研究成果汇集整理，形成对NFA非确定性量化这一复杂主题的清晰图景。

4. 方法论

这篇论文作为一篇综述，其“方法论”主要体现在对现有概念、定义、分类和定理的系统性梳理和阐述上。它没有提出新的算法或模型，而是将已有的研究成果组织起来，以探讨“歧义性、非确定性及其状态复杂性”这一主题。因此，本节将详细阐述论文中定义的各种量化指标及其分类方法，这些构成了论文分析的基础。

4.1. 方法原理

论文的核心思想是通过量化非确定性（Nondeterminism）和歧义性（Ambiguity）来更细致地理解非确定性有限自动机（NFA）的计算能力和描述简洁性。NFA 的非确定性是一个广义概念，它可以从多个角度进行度量：

1. 歧义度 (Degree of Ambiguity): 关注一个 NFA 接受一个字符串时有多少条不同的成功计算路径。这直接反映了语言的“模糊性”或“多重解释性”。

2. 计算中的猜测量 (Amount of Guessing): 关注在单次计算过程中，每一步转移所包含的非确定性选择的数量。这反映了 NFA 在决策时的“分支程度”。

3. 计算树的结构 (Structure of the Computation Tree): 关注一个 NFA 对一个字符串进行计算时，所有可能路径形成的树状结构，特别是其叶子数量。这反映了所有可能计算路径的复杂性。

   通过对这些指标的量化，研究人员能够将 NFA 划分为不同的复杂度类别（例如，无歧义、有限歧义、多项式歧义、指数歧义；或有界猜测、有界树宽度等），进而比较这些类别在状态复杂性上的差异。其背后的理论基础在于，非确定性的“程度”越高，理论上自动机在识别相同语言时所需的 states 就越少，从而越简洁。反之，限制非确定性将导致自动机状态数量的增加，甚至可能是指数级的增加。

4.2. 核心方法详解 (概念和度量定义)

论文详细定义了各种度量 NFA 歧义性和非确定性的方法。

4.2.1. NFA 的基本定义与计算

一个非确定性有限自动机 (NFA) 定义为一个五元组 $A = (Q, \Sigma, \delta, q_0, F)$：

• $Q$: 有限状态集合。

• $\Sigma$: 输入字母表。

• $\delta: Q \times \Sigma \to 2^Q$: 转移函数，从一个状态和一个输入符号映射到可能的一组状态。

• $q_0 \in Q$: 初始状态。

• $F \subseteq Q$: 接受状态集合。

  一个 NFA $A$ 在字符串 $w = b_1 b_2 \cdots b_k$ (其中 $b_i \in \Sigma$, $i = 1, \ldots, k$, $k \geq 0$) 上的一个计算 (computation) 是一个状态序列 $(p_1, \ldots, p_\ell)$，其中 $p_1 \in \delta(q_0, b_1)$，且 $p_{j+1} \in \delta(p_j, b_{j+1})$ 对 $j=1, \ldots, \ell-1$ 成立。

• 如果 $\ell = k$，则称其为 完整计算 (complete computation)。

• 如果 $\ell = k$ 且 $p_k \in F$，则称其为 接受计算 (accepting computation)。

• NFA $A$ 接受语言 $L(A) = \{ w \in \Sigma^* \mid \delta(q_0, w) \cap F \neq \emptyset \}$。

4.2.2. 歧义度 (Degree of Ambiguity)

NFA $A$ 在字符串 $w$ 上的歧义度 $\mathrm{da}_A(w)$ 定义为 $A$ 在 $w$ 上接受计算的数量。

• 长度为 $m$ 的字符串上的最大歧义度: $$\mathrm{da}_A (m) = \max \{ \mathrm{da}_A (w) \mid w \in \Sigma^m \}$$ 其中，$\mathrm{da}_A(m)$ 是一个从自然数到自然数的函数。
• 总歧义度: $$\mathrm{da}_A^{\mathrm{sup}} = \sup_{m \in \mathbb{N}} \mathrm{da}_A (m)$$ 如果这个上界是有限的，则称 NFA 为 有限歧义 (finitely ambiguous)。

根据歧义度的增长率，NFA 分为以下几类：

• DFA (Deterministic Finite Automaton): 确定性有限自动机。
• UFA (Unambiguous NFA): 无歧义 NFA，即 $\mathrm{da}_A^{\mathrm{sup}} = 1$。每个字符串至多有一个接受计算。所有 DFA 都是 UFA。
• FNFA (Finitely Ambigous NFA): 有限歧义 NFA，即 $\mathrm{da}_A^{\mathrm{sup}}$ 是一个有限常数。
• PNFA (Polynomially Ambigous NFA): 多项式歧义 NFA。如果 $A$ 不是有限歧义的，但存在一个多项式 $p(\cdot)$ 使得 $\mathrm{da}_A(m) \leq p(m)$ 对所有 $m \in \mathbb{N}$ 成立，则称 $A$ 为严格多项式歧义。其多项式增长度 (polynomial degree of growth) 是上界函数 $\mathrm{da}_A(m)$ 的最小多项式 p'(m) 的度数。
• 一般 NFA (General NFA): 如果 $A$ 不是多项式歧义的，则称其为严格指数歧义 NFA，其歧义度通常呈指数增长。

4.2.3. 非确定性度量 (Nondeterminism Measures)

这些度量关注计算过程中的“猜测”量或计算路径的复杂性。

1. 猜测 (Guessing) $\gamma_A(C)$: 对于 NFA $A = (Q, \Sigma, \delta, q_0, F)$ 和字符串 $w = b_1 b_2 \cdots b_k$，以及一个计算 $C = (p_1, \ldots, p_\ell)$，其中 $p_1 \in \delta(q_0, b_1)$ 且 $p_{j+1} \in \delta(p_j, b_{j+1})$。计算 $C$ 的猜测量 $\gamma_A(C)$ 定义为： $$\gamma_A (C) = \log_2 { \left| \delta ( q_0 , b_1 ) \right| } + \sum_{i=1}^{\ell-1} \log_2 { \left| \delta ( p_i , b_{i+1} ) \right| }$$ 符号解释:

   • $\gamma_A(C)$: 计算 $C$ 的猜测量。
   • $\log_2$: 以 2 为底的对数，表示信息比特数。
   • $|\delta(q, b)|$: 转移函数 $\delta$ 在状态 $q$ 和符号 $b$ 下可能转移到的状态数量。这个值越大，表示非确定性选择越多。
   • $q_0$: NFA 的初始状态。
   • $b_1$: 字符串 $w$ 的第一个符号。
   • $p_i$: 计算路径中的第 $i$ 个状态。
   • $b_{i+1}$: 字符串 $w$ 的第 $(i+1)$ 个符号。
   • $\ell$: 计算路径的长度（状态序列中的状态数量）。 直观上，$\gamma_A(C)$ 代表了在计算 $C$ 过程中所使用的“猜测”量，以信息比特数表示。如果 NFA 是一个 DFA，则所有 $| \delta(q, b) | = 1$，因此 $\log_2 1 = 0$，猜测量为零。

2. 字符串的猜测量 $\gamma_A(w)$ 和最大猜测量 $\gamma_A^{\mathrm{max}}(w)$:

   • 对于接受语言 L(A) 的字符串 $w \in L(A)$，其猜测量 $\gamma_A(w)$ 定义为最佳接受计算的猜测量： $$\gamma_A (w) = \min \{ \gamma_A (C) \mid C \in \mathrm{comp}_A^{\mathrm{acc}} (w) \}$$ 符号解释:
     • $\mathrm{comp}_A^{\mathrm{acc}}(w)$: NFA $A$ 在字符串 $w$ 上所有接受计算的集合。
   • NFA $A$ 在字符串 $w \in \Sigma^*$ 上的最大猜测量 $\gamma_A^{\mathrm{max}}(w)$ 定义为所有计算（不限于接受计算）的最大猜测量： $$\gamma_A^{\mathrm{max}} (w) = \max \{ \gamma_A (C) \mid C \in \mathrm{comp}_A (w) \}$$ 符号解释:
     • $\mathrm{comp}_A(w)$: NFA $A$ 在字符串 $w$ 上所有计算的集合。

3. 分支 (Branching) $\beta_A(C)$: 计算 $C$ 的分支 $\beta_A(C)$ 定义为单个转换分支的乘积，或表示为 $\beta_A(C) = 2^{\gamma_A(C)}$。

4. 跟踪 (Trace) $\tau_A(w)$: NFA $A$ 在字符串 $w$ 上的跟踪 $\tau_A(w)$ 定义为 $\tau_A(w) = 2^{\gamma_A^{\mathrm{max}}(w)}$。

5. 计算树宽度 (Tree Width) $\mathrm{tw}_A(w)$: NFA $A$ 在字符串 $w$ 上所有计算的总数量，即计算树的叶子数量。 $$\mathrm{tw}_A (w) = | \mathrm{comp}_A (w) |$$ 它在 [19] 中也被称为“叶子大小 (leaf size)”。

4.2.4. 增长率函数 $\chi_A(m)$

与歧义度类似，上述非确定性度量也可以定义为输入长度 $m$ 的函数。对于任何度量 $\chi \in \{ \mathrm{tw}, \gamma, \gamma^{\mathrm{max}}, \beta, \tau \}$，函数 $\chi_A: \mathbb{N} \to \mathbb{N}$ 定义为： $$\chi_A (m) = \max \{ \chi_A (w) \mid w \in \Sigma^m \} , \quad m \in \mathbb{N}$$ 如果 $\chi_A^{\mathrm{sup}} = \sup_{m \in \mathbb{N}} \chi_A (m)$ 是有限的，则称该函数是有限的。

4.2.5. 状态复杂性比较术语

• 超多项式分离 (Super-polynomially separated): 考虑设备类别 $X$ 和 $Y$ (例如 DFA, UFA, FNFA, PNFA, 通用 NFA)。如果存在一系列语言 $L_n$ (对于 $n \in \mathbb{N}$)，其中 $L_n$ 可以被 $Y$ 类中具有 $n$ 个状态的设备识别，但对于任何多项式 p(n) 和足够大的 $n$，识别 $L_n$ 的 $X$ 类设备需要超过 p(n) 个状态，那么称 $Y$ 类与 $X$ 类是超多项式分离的。这大致意味着从 $Y$ 类模拟到 $X$ 类，最坏情况下会导致超多项式大小的膨胀。

这些定义和分类构成了论文分析和比较各种 NFA 模型的基础，使得后续讨论不同非确定性/歧义性级别下的状态复杂性权衡成为可能。

5. 实验设置

作为一篇综述性质的论文，它并没有进行传统的“实验”，即没有运行具体的代码或在特定的数据集上训练模型。因此，本节将根据综述论文的特性，将“实验设置”理解为研究问题提出的语境、用于分析的“数据”类型以及“评估”这些研究成果所用的指标和比较基线。

5.1. 数据集

在关于自动机状态复杂性的研究中，“数据集”通常指的是用于展示特定复杂性属性的正则语言族 (families of regular languages) 或特定构造的 NFA 族 (families of NFAs)。这些语言或 NFA 通常是经过精心设计的，以揭示不同自动机模型之间描述简洁性的差异。

论文中提及的一些典型“数据集”示例包括：

• Leung [30] 用于分离 NFA 和 PNFA 的语言族： $L_n = (0 + (01^*)^{n-1}0)^*$，其中 $n \geq 1$。

  • 特点： 这种语言族可以被一个 $n$ 状态的指数歧义 NFA 识别，但任何等价的 PNFA 都需要显著更多的状态。
  • 目的： 展示一般 NFA 比 PNFA 具有超多项式简洁性优势。

• Goldstine et al. [11] 用于展示有限分支 NFA 频谱结果的语言： 论文提到了使用一个最小 DFA，其大小为 $2^n-1$。具体的语言构造是用来展示 NFA 具有不同有限分支数量时，所需状态数的变化。

  • 目的： 揭示 NFA 在不同有限非确定性（特别是分支）约束下，状态复杂性如何渐进变化。

• Palioudakis et al. [38] 用于有限树宽度 NFA 的语言族： 构造了具有树宽度 $k$ 的 $n$ 状态 NFA $A_{n,k}$，用于确定转换到 DFA 的状态复杂度下界。

  • 目的： 量化有限树宽度 NFA 转换为 DFA 的状态膨胀。

• Hromkovi and Schnitger [20] 用于分离 PNFA 和 FNFA 的语言 $L_{r,k}$： 构造了具有多项式歧义度的语言，证明了其等价的 FNFA 需要超多项式数量的状态。

  • 目的： 证明 PNFA 与 FNFA 之间的超多项式分离。

    这些“数据集”并非真实世界的数据，而是理论计算机科学中常用的构造性示例 (constructive examples)，它们被设计用来证明特定复杂性界限或分离结果，验证理论假设。

5.2. 评估指标

论文中“评估”各种 NFA 模型及其非确定性量化的核心指标是状态复杂性 (state complexity)，通常以状态数量 (number of states) 来衡量。具体来说，涉及以下几个方面：

1. NFA 的状态数量 ($n$): 这是衡量自动机大小的基本单位。
2. DFA 的状态数量: 用于与 NFA 进行比较，尤其是在确定化过程中的状态膨胀。
3. 歧义度增长率:
   • 有界 (Bounded): 常数，例如 UFA ($k=1$) 或 FNFA ($k > 1$)。
   • 多项式 (Polynomial): p(m)，表示 PNFA。
   • 指数 (Exponential): $2^{\Theta(m)}$。
4. 非确定性度量增长率:
   • 有界 (Bounded): 常数，例如有限猜测、有限分支、有限树宽度。
   • 次线性 (Sublinear): 例如 $\Theta(\sqrt[k]{m})$。
   • 线性 (Linear): $\Theta(m)$。
   • 多项式 (Polynomial): p(m)。
   • 指数 (Exponential): $2^{\Theta(m)}$。
5. 状态膨胀倍数: 衡量从一种自动机类型转换到另一种类型时，状态数量增加的比例，例如 $2^n - 1$ (指数级膨胀) 或 p(n) (多项式膨胀)。

评估指标说明：

• 状态数量 (Number of States):

  1. 概念定义: 衡量一个有限自动机识别给定语言所需的基本存储单元（即内部状态）的数量。在描述复杂性中，状态数量通常被视为自动机“大小”的直接指标。更小的状态数量意味着更简洁、可能更高效的自动机。
  2. 数学公式: 该指标没有具体的数学公式，因为它是一个计数。通常表示为 $|Q|$，其中 $Q$ 是状态集合。
  3. 符号解释: $Q$ 代表自动机的状态集合，其基数 $|Q|$ 即为状态数量。

• 增长率 (Growth Rate):

  1. 概念定义: 描述了某种度量（如歧义度 $\mathrm{da}_A(m)$ 或猜测量 $\gamma_A(m)$）随输入长度 $m$ 增加的趋势。它用于将自动机分类为不同复杂性等级。
  2. 数学公式: 通常使用大 O 符号 (Big O notation)、大 $\Omega$ 符号 (Big Omega notation) 或大 $\Theta$ 符号 (Big Theta notation) 来表示。
     • 有界 (Bounded): $O(1)$。
     • 线性 (Linear): $O(m)$ 或 $\Theta(m)$。
     • 多项式 (Polynomial): $O(m^k)$ 或 $\Theta(m^k)$ 对于某个常数 $k > 0$。
     • 指数 (Exponential): $O(c^m)$ 或 $\Theta(c^m)$ 对于某个常数 $c > 1$。
  3. 符号解释:

     • $m$: 输入字符串的长度。

     • $O(\cdot)$, $\Omega(\cdot)$, $\Theta(\cdot)$: 渐进符号，用于描述函数在输入趋于无穷大时的行为。

     • $k$: 多项式的度数。

     • $c$: 指数函数的底数。

       这些指标共同构成了对 NFA 非确定性、歧义性及其对描述简洁性影响的全面“评估”框架。

5.3. 对比基线

论文中的“对比基线”是不同类型的有限自动机或具有不同量化非确定性/歧义性限制的 NFA。这些基线用于比较特定语言的描述简洁性。

主要对比基线包括：

1. 自动机类型:

   • DFA (Deterministic Finite Automaton): 作为最受限制的自动机类型，通常是所有比较的“上限”，因为 NFA 转换为 DFA 往往会导致状态膨胀。
   • UFA (Unambiguous NFA): 无歧义 NFA，比 DFA 允许更多非确定性，但仍限制了接受路径的唯一性。
   • FNFA (Finitely Ambigous NFA): 有限歧义 NFA，比 UFA 允许更多的接受路径，但数量是常数。
   • PNFA (Polynomially Ambigous NFA): 多项式歧义 NFA，歧义度随输入长度多项式增长。
   • NFA (General NFA): 没有任何歧义度限制的通用非确定性有限自动机，其歧义度可能是指数级的。

2. 非确定性量化级别:

   • 有限猜测 (Finite Guessing) / 有限分支 (Finite Branching): 猜测量或分支数是常数的 NFA。

   • 有限树宽度 (Finite Tree Width): 计算树的叶子数量是常数的 NFA。

   • 有界次线性猜测 (Bounded Sublinear Guessing): 猜测量增长慢于线性（如 $\Theta(\sqrt[k]{m})$）。

     论文通过比较这些基线来回答核心问题：一个 NFA 允许的非确定性和歧义性越多，它是否能用更少的 states 来描述一个语言？以及这种节省是多项式还是指数级的？这些比较通常通过构造特定的语言族和证明状态数量的下界来完成。

6. 实验结果与分析

这篇综述论文的“实验结果”并非传统意义上的数值数据，而是一系列关于 NFA 歧义度、非确定性度量及其状态复杂性权衡的理论定理和分离结果。这些定理通过严谨的数学证明（通常涉及构造特定的语言族或自动机）来确立不同自动机模型之间的简洁性界限和相互关系。

6.1. 核心结果分析

6.1.1. 歧义度的可判定性与增长率

• 定理 1 (Weber and Seidl [50]): 可以在多项式时间内判定一个给定的 NFA 是有限歧义、严格多项式歧义还是严格指数歧义。此外，多项式歧义 NFA 的多项式增长度也可以在多项式时间内计算。
  • 分析: 这是一个重要的算法结果，意味着我们能够有效地分类 NFA 的歧义性。它表明 NFA 的歧义度增长率（有界、多项式、指数）不是任意的，而是可以被算法区分的。
• 定理 2 (Chan and Ibarra [5]): 对于给定的 NFA $A$ 和 $k \in \mathbb{N}$，测试 $A$ 的歧义度是否至少为 $k$ 是 PSPACE 完全的。
  • 分析: 尽管我们可以分类 NFA 的歧义类型，但精确确定其有限歧义度是否达到某个给定值 $k$ 是计算上困难的（PSPACE 完全），这暗示了有限歧义 NFA 内部的复杂性。
• 定理 3 (Weber and Seidl [50]): 一个 $n$ 状态的 FNFA 的歧义度最多为 $5^{\frac{n}{2}} \cdot n^n$。
  • 分析: 提供了有限歧义 NFA 在最坏情况下的歧义度上界。虽然这个上界是指数级的，但对于某些子类，最大有限歧义度可以精确到 $2^{\Theta(n)}$。这说明即使是有限歧义的 NFA，其歧义度也可以非常大。

6.1.2. 歧义性与状态复杂性

• 定理 4 (Leiss [29], Leung [32]):
  1. 对于每个 $n \in \mathbb{N}$，存在一个 $n$ 状态的 UFA，其最小等价 DFA 有 $2^n - 1$ 个状态。
  2. 对于每个 $n \in \mathbb{N}$，存在一个 $n$ 状态的 FNFA，其任何等价 UFA 都有 $2^n - 1$ 个状态。
  • 分析: 这两个结果是描述复杂性中的经典分离结果。它们表明，即使是无歧义的非确定性（UFA），与确定性（DFA）相比也能带来指数级的状态节省。更进一步，即使允许有限的歧义性（FNFA），相对于严格的无歧义性（UFA），也能带来指数级的节省。这意味着在自动机设计中，允许少量非确定性或歧义性可以显著提高简洁性。
• 定理 5 (Ravikumar and Ibarra [42]): 任何接受有界语言 (bounded language) 的 NFA 都可以转换为一个 FNFA，状态膨胀最多是多项式级别。识别有界语言的 FNFA 类（或 UFA 类）与对应的 UFA 类（或 DFA 类）是超多项式分离的。
  • 分析: 对于一类特定的语言（有界语言），一般 NFA 可以在多项式状态膨胀下转换为 FNFA，这与一般正则语言的情况不同。然而，对于有界语言，FNFA 和 UFA (以及 UFA 和 DFA) 之间仍然存在显著的超多项式简洁性分离，强调了即使在这种受限情况下，歧义性的不同级别也具有强大的区分能力。
• 定理 6 (Leung [30], Hromkovi et al. [19]): NFA 类与 PNFA 类是超多项式分离的。
  • 分析: 这是一个非常重要的结果，表明通用 NFA 比多项式歧义 NFA 在简洁性上具有指数级甚至更高的优势。Leung 的原始证明给出了 $2^n - 1$ 的最优状态膨胀，Hromkovi 等人的通信复杂性方法提供了更普适的证明。这意味着，如果一个语言只能被指数歧义的 NFA 以 $n$ 状态识别，那么任何多项式歧义的 NFA 都需要超多项式数量的状态。
• 定理 7 (Hromkovi and Schnitger [20]): 对于 $n \in \mathbb{N}$，存在一个状态数在 $n$ 的多项式范围内的 PNFA $A$，其识别的语言 L(A) 的任何 FNFA 都至少需要 $2^{\Omega(n^{1/3})}$ 个状态。
  • 分析: 解决了长期开放的问题，证明了多项式歧义 NFA (PNFA) 与有限歧义 NFA (FNFA) 之间也存在超多项式分离。这意味着即使歧义度只是多项式增长，也比有限歧义 NFA 更具简洁性。
• 定理 8 (Hromkovi and Schnitger [20]): 给出了更普遍的结论，表明歧义度为 $O(m^k)$ 的 NFA 与歧义度为 $o(m^k)$ 的 NFA 之间存在超多项式分离。
  • 分析: 这个定理泛化了定理 7，说明了不同多项式增长度的歧义 NFA 之间也存在简洁性上的层级。它进一步细化了歧义度对状态复杂性的影响。

6.1.3. 非确定性度量

• 定理 9 (Hromkovi et al. [19]): 对于任何 NFA $A$，函数 $\mathrm{tw}_A(m)$ 要么是有界常数，要么在 $m$ 的线性到多项式之间，要么在 $2^{\Theta(m)}$ 之间。
  • 分析: 刻画了计算树宽度 (tree width) 的可能增长率。与歧义度类似，它不能是无界但次线性的。这提供了一个重要的结构性洞察。
• 定理 10 (Leung [31]): 对于给定的 NFA $A$，判定 $\gamma_A(m)$ 是否有界是 PSPACE 完全的。
  • 分析: 尽管树宽度的有界性可以有效地判定，但判断猜测量 (guessing) 的有界性却非常困难（PSPACE 完全），这表明猜测量比树宽度更难分析。
• 定理 11 (Simon [48], Goldstine et al. [12]): 对于每个 $k \in \mathbb{N}$，存在一个 NFA $A$ 使得 $\gamma_A(m) = \Theta(\sqrt[k]{m})$。
  • 分析: 证明了猜测量函数可以是无界且次线性的，这与歧义度 ($\mathrm{da}_A(m)$) 和树宽度 ($\mathrm{tw}_A(m)$) 的增长模式不同。这是一个显著的差异，表明猜测量可以以比线性更慢的速度无限制增长。
• 定理 12 (Leung [31]): 如果 $A$ 是一个具有有界猜测的 $n$ 状态 NFA，那么 $\gamma_A^{\mathrm{sup}} = O(2^n)$。存在 $n$ 状态 NFA $B_n$ 使得 $\gamma_{B_n}^{\mathrm{sup}} = 2^{n/3} - 2$。
  • 分析: 给出了有界猜测 NFA 的猜测量上界，并展示了即使猜测量有界，其最大值也可以非常大（指数级）。
• 定理 13 (Palioudakis et al. [38]): 一个 $n$ 状态有限树宽度 NFA 的树宽度最多为 $2^{n-2}$。对于每个 $n \geq 2$ 和 $1 \leq k \leq 2^{n-2}$，存在一个 $n$ 状态二进制字母表 NFA 具有最优树宽度 $k$。
  • 分析: 提供了有限树宽度 NFA 的树宽度精确上界，并证明了所有可能的值都可以实现。这个上界比有限歧义度的上界要小。

6.1.4. 非确定性度量与歧义度的比较

• 命题 1 (Palioudakis et al. [39]): 如果 $A$ 是一个有限树宽度 NFA，则 $\mathrm{tw}_A^{\mathrm{sup}} \leq \tau_A^{\mathrm{sup}} \leq 2^{\mathrm{tw}_A^{\mathrm{sup}} - 1}$。
  • 分析: 建立了有限树宽度与跟踪 (trace) 之间的关系。这意味着如果树宽度有限，则跟踪也有限，并且它们之间存在一个指数关系。
• 定理 14 (Hromkovi et al. [19]): 如果 $A$ 是一个最小 NFA，那么对于所有 $m \in \mathbb{N}$，$\max(\gamma_A^{\max}(m), \mathrm{da}_A(m)) \leq \mathrm{tw}_A(m) = O(\mathrm{da}_A(m) \cdot \gamma_A^{\max}(m))$。
  • 分析: 这是非确定性度量之间的一个重要关系。它表明计算树宽度至少与最大猜测量和歧义度中的较大者相当，且最多是两者乘积的多项式。这量化了这些度量之间的相互依赖性。
• 定理 15 (Goldstine et al. [12]): 如果 NFA $A$ 的 $\gamma_A(m)$ 是非常数且次线性的，则 $A$ 的完整歧义度必须是无界的。反之，如果 $\gamma_A(m)$ 是 $O(1)$ 或 $\Theta(m)$，则完整歧义度可以是有界或无界。
  • 分析: 揭示了猜测量与歧义度之间一个微妙的关系。次线性的无界猜测量必然导致无界歧义度，这在一定程度上限制了歧义度的增长模式，而有界或线性猜测量则不一定。

6.1.5. 有限非确定性与状态复杂性

• 定理 16 (Goldstine et al. [11]): 对于每个 $n \in \mathbb{N}$，存在一个 $n$ 状态 NFA $A$，其任何识别 L(A) 的有限分支 NFA 都至少需要 $2^{n-1}$ 个状态。
  • 分析: 证明了将一般 NFA 转换为有限分支 NFA 可能会导致指数级状态膨胀。这强调了无界分支非确定性的强大简洁性。
• 定理 17 (Goldstine et al. [11]): 对于一个大小为 $2^n - 1$ 的最小 DFA $A$，当 $2 \leq k \leq \frac{n}{\log_2 n}$ 时，具有分支 $k$ 的最优 NFA 大小至少为 $2^{n/k}$；当 $k \geq \frac{n}{\log_2 n}$ 时，具有分支 $k$ 的最优 NFA 大小至少为 $n$。
  • 分析: 这个定理是“频谱结果”的一部分，它给出了对于一个复杂语言，不同有限分支量 $k$ 对 NFA 状态数量下界的影响。随着 $k$ 的增加，状态数量的下界逐渐减小。
• 定理 18 (Goldstine et al. [11]): 补充了定理 17，给出了一个 $n+1$ 状态 NFA $A_n$，展示了其语言在不同分支 $k$ 下最优 NFA 大小的具体范围。
  • (i) $\sigma_n[1] = 2^n$，且 $2^{n/k} \leq \sigma_n[k] < 2k \cdot 2^{n/k}$ 当 $2 \leq k < \frac{n}{\log_2 n}$ 时。
  • (ii) $n+1 \leq \sigma_n[k] < 2k \cdot 2^{n/k}$ 当 $\frac{n}{\log_2 n} \leq k < n$ 时。
  • (iii) $n+1 \leq \sigma_n[k] < 4n$ 当 $k \geq n$ 时。
  • 分析: 定理 17 和 18 共同构成了关于有限分支 NFA 的“频谱结果”。它们精确地量化了在给定一个语言时，允许更多有限量的分支如何带来渐进的状态节省。从 $k=1$ (DFA) 的 $2^n$ 到 $k \geq n$ 时的 $n+1$，状态数量实现了显著的减少。
• 定理 19 (Palioudakis et al. [38]): 对于一个具有最多 $k \leq n-1$ 树宽度的 $n$ 状态 NFA $A$，语言 L(A) 具有一个大小为 $1 + \sum_{j=1}^{k} \binom{n-1}{j}$ 的 DFA。此外，对于每个 $1 \leq k \leq n-1$，存在一个 $n$ 状态 NFA $A_{n,k}$ 具有树宽度 $k$，其最小 DFA 需要 $1 + \sum_{j=1}^{k} \binom{n-1}{j}$ 个状态。
  • 分析: 这个结果非常重要，它表明有限树宽度 NFA 转换为 DFA 只会产生多项式状态膨胀，而不是通常的指数级。这与有限分支 NFA 的情况形成对比，后者仍然可能需要指数级的 DFA 状态。这说明树宽度是一个比分支更强的限制。
• 定理 20 (Kappes [23]): 一个具有 $n$ 状态和分支 $k$ 的 NFA 可以被一个具有 $k \cdot n$ 状态和 $k$ 个初始状态的 MDFA (Deterministic finite automata with multiple initial states) 模拟。
  • 分析: 提供了有限分支 NFA 到 MDFA 的一个有效模拟方法，显示出 MDFA 在某些情况下可以有效利用有限的非确定性。Palioudakis et al. [40] 提供了几乎匹配的下界。

6.2. 数据呈现 (表格)

由于原文中没有直接的实验结果表格，而是以定理的形式呈现理论结果，因此我将这些定理本身视为“数据”，并进行分析。对于其中涉及数值比较的部分，将在核心结果分析中进行阐述。

7. 总结与思考

7.1. 结论总结

这篇综述论文对有限自动机中歧义度 (ambiguity) 和各种非确定性 (nondeterminism) 度量及其对状态复杂性 (state complexity) 的影响进行了全面而深入的总结。主要结论包括：

1. 歧义度的层次结构与简洁性优势： NFA 的歧义度可以分为无歧义 (UFA)、有限歧义 (FNFA)、多项式歧义 (PNFA) 和通用 (指数歧义) NFA。这些类别之间存在严格的简洁性层次结构，从 DFA 到 UFA、FNFA、PNFA 再到通用 NFA，每向前一步都可能带来超多项式甚至指数级的状态节省。例如，将 UFA 确定化可能导致指数级状态膨胀，而通用 NFA 比 PNFA 和 PNFA 比 FNFA 都具有超多项式简洁性优势。

2. 非确定性度量的多样性与特性： 非确定性可以通过多种方式量化，如计算中的 猜测 (guessing)、分支 (branching)、跟踪 (trace) 和 计算树宽度 (tree width)。这些度量具有不同的增长率模式：树宽度与歧义度一样，不能是无界次线性的，但猜测量可以是无界次线性的。

3. 度量间的关系与转化： 论文阐明了这些度量之间的相互关系，例如计算树宽度与最大猜测量和歧义度之间的关联。有限树宽度 NFA 可以转换为多项式大小的 DFA，这与一般 NFA 的指数级转换形成对比，显示出树宽度作为限制条件的强大效果。

4. 有限非确定性的“频谱效应”： Goldstine et al. 的工作揭示了，对于特定语言，允许不同“有限”数量的分支 (branching) 可以带来渐进的状态节省，形成一个状态复杂性的“频谱”。这表明非确定性并非一个简单的二元概念，其量的变化能精细地影响自动机的简洁性。

5. 可判定性与复杂性： NFA 歧义类型的判定是多项式时间可解的，但精确确定其有限歧义度或猜测量是否达到某个值却是 PSPACE 完全问题，揭示了这类问题的内在计算困难性。

   总而言之，该论文清晰地描绘了 NFA 非确定性量化研究的图景，强调了非确定性在描述复杂性中的关键作用，并为该领域的进一步探索奠定了基础。

7.2. 局限性与未来工作

作者在论文的“结论与开放问题”部分明确指出了当前的局限性，并提出了以下未来研究方向：

1. 无界非确定性度量下的状态复杂性： 目前关于无界非确定性（如无界分支或无界树宽度）作为输入长度函数时 NFA 状态复杂性的研究非常少。这是一个重要的空白，需要探讨这些情况下 NFA 的简洁性如何与 DFA 或其他受限 NFA 比较。
2. 不同无界度量之间的简洁性比较： 尽管存在有限歧义、多项式歧义和通用 NFA 之间的超多项式分离，但对于不同无界分支或无界树宽度 NFA 之间的简洁性比较，目前尚无已知结果。
3. 通信复杂性技术的应用： 作者特别提出，Hromkovi et al. [19, 20] 用于分离不同歧义度 NFA 的强大通信复杂性技术，是否可以应用于为那些分支或树宽度作为输入长度函数的 NFA 的状态复杂性建立好的下界和分离结果。
4. 歧义度与非确定性度量之间的交叉比较： 进一步研究给定歧义度 NFA 与给定分支（或树宽度）NFA 之间的简洁性比较。目前这方面的结果还很少。
5. 树宽度频谱结果的缺失： 类似于分支度量的“频谱结果” (Theorem 18)，树宽度度量缺乏类似的结果，即对于一个给定的语言序列，缺乏关于不同树宽度值下 NFA 简洁性的良好界限。

7.3. 个人启发与批判

7.3.1. 个人启发

这篇综述论文提供了几个重要的启发：

• 非确定性的精细化视角： 过去常将非确定性视为一个二元概念（有或无），但论文展示了非确定性是一个可以被精细量化的谱系。不同的量化方式（歧义度、猜测、树宽度）捕捉了非确定性行为的不同方面，并且这些细微的差异在自动机的简洁性上产生了巨大的影响。这提示我们在设计和分析计算模型时，应更深入地思考其非确定性机制。
• 理论复杂性与实际应用： 尽管这些研究主要集中在理论计算机科学领域，但对于编译器设计（正则表达式到自动机）、程序验证和形式化方法等领域，理解不同自动机模型之间的转换成本和简洁性权衡具有实际意义。例如，当需要将一个 NFA 转换为 DFA 时，知道 NFA 的歧义度或树宽度可以帮助我们预测转换后的 DFA 大小，从而选择最优的转换策略。
• 通信复杂性方法的强大： 论文多次提到通信复杂性技术在证明状态复杂性下界和分离结果方面的强大作用。这启发我们，跨领域的理论工具（如通信复杂性）能够为看似不相关的领域（如自动机理论）带来突破性的进展。
• 开放问题作为研究的驱动力： 论文明确列出的开放问题不仅指明了未来研究方向，也展示了理论计算机科学作为一个活跃领域，仍有大量基础且重要的问题有待探索。特别是关于无界非确定性度量的状态复杂性，这可能是一个富饶的研究领域。

7.3.2. 批判

尽管这篇综述非常全面和有价值，但仍有一些可以思考或改进的地方：

• 对初学者的阅读难度： 尽管我被要求以初学者友好的方式解释，但论文本身对初学者来说可能仍然相当密集。一些概念（例如通信复杂性）的背景知识并未在论文中深入解释，读者可能需要查阅更多资料才能完全理解其证明思想。作为一篇综述，这在所难免，但如果能在概述中对这些高级技术做更直观的类比，可能会更有帮助。
• 非确定性度量的实用性比较： 论文详细定义了多种非确定性度量，并分析了它们之间的理论关系。然而，对于哪种度量在实际应用场景中更具解释性或指导意义，论文探讨较少。例如，在实际的正则表达式匹配引擎设计中，究竟是“猜测量”还是“计算树宽度”更能反映其性能瓶颈？
• 最新进展的及时性： 鉴于论文发表于 2016/2017 年，自那时以来，该领域可能已经有了新的进展和开放问题的解决。一篇最新的综述可能会包含更多近年来利用新工具（例如基于逻辑的方法、机器学习与自动机理论的交叉）解决相关问题的成果。
• 对“冗余”非确定性的讨论： 论文在讨论 有限猜测 NFA 时提到，“冗余的非确定性”是一个开放问题，即是否存在 $n$ 状态 NFA 具有比 $n$ 更大的有界猜测量，且不能被相同大小但更少非确定性的 NFA 识别。这个概念本身非常有趣，但论文中对其讨论较少，未能深入探讨如何形式化“更少非确定性”这一概念以及如何进行比较。