paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Minimization of visibly pushdown automata is NP-complete

可见下推自动机的最小化是 NP 完全的
LMCS vol.Volume 16, Issue 12020匹配度 2/10 · 该论文研究可见下推自动机最小化的计算复杂性，属于自动机与形式语言理论，与用户关注的 LLM/Agent 结合静态分析、浮点程序分析或贝叶斯程序分析等核心方向没有直接交集。虽然形式化方法/程序分析可能间接依赖自动机理论，但这篇论文本身是纯理论复杂性结果，不涉及用户当前追的问题。引用 9 inbox
Olivier Gauwin, Anca Muscholl, Michael Raskin
逻辑与自动机
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话：证明可见下推自动机最小化问题是 NP 完全的，并借助 immersions 给出归约。

本文研究可见下推自动机（VPA）最小化问题的计算复杂度。作者证明该问题是 NP 完全的。证明首先引入 immersions：这类对象在普通（非可见）字母表上，用同一个确定性转移图识别多个语言，每个语言由初始状态和终态集合确定；作者证明 immersions 的最小化也是 NP 完全的，然后将其归约到可见下推自动机的最小化。该工作给出了 VPA 最小化复杂度的精确刻画，表明不存在多项式时间算法（除非 P=NP），并建立了不同自动机最小化问题之间的联系。

问题
可见下推自动机的最小化问题是否可在多项式时间内求解，其精确复杂度如何。
方法
引入 immersions 作为中间模型，证明其最小化是 NP 完全的，再通过归约将结果传递到 visibly pushdown automata 的最小化问题。
评估
以理论复杂度归约和证明进行评估，给出 visibly pushdown automata 最小化的 NP 完全性结论。
原文摘要（Abstract）

We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-visible alphabet) using a common deterministic transition graph, such that each language is associated with an initial state and a set of final states. We show that minimizing immersions is NP-complete, and reduce this problem to the minimization of visibly pushdown automata.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@article{GauwinMR19,
  title = {Minimization of visibly pushdown automata is NP-complete},
  author = {Olivier Gauwin and Anca Muscholl and Michael Raskin},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 1},
  year = {2020},
  doi = {10.23638/lmcs-16(1:14)2020}
}