paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Higher-order parity automata

高阶奇偶自动机
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 2/10 · 该论文是高阶奇偶自动机与高阶模型检查的纯理论工作,属于形式语义/自动机理论,与用户关注的静态分析、浮点/贝叶斯程序分析以及 LLM 与静态分析/形式化验证的交叉均无直接关联,也未涉及工具落地或 benchmark。引用 19 inbox
Paul-André Melliès
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:提出高阶奇偶自动机,将奇偶树自动机推广到无穷简单类型 λ-项,并证明由 λY-项生成的项接受性可判定。

本文把经典奇偶树自动机从无穷有序树推广到无穷简单类型 λ-项,提出高阶奇偶自动机的概念。主要结果为:当无穷 λ-项由有限简单类型 λY-项生成时,该高阶奇偶自动机对它的接受性是可判定的。证明思路融合线性逻辑、指称语义与无穷重写理论:借助线性逻辑揭示 λ-项与自动机之间的对偶结构,用指称语义刻画无穷项的语义行为,并通过无穷重写理论处理归约与求值过程,从而构造出判定过程。该工作拓展了高阶模型检测与无穷项自动机理论的理论基础。

问题
如何将有限秩树上的奇偶树自动机推广到无穷简单类型 λ-项,并判定这类无穷项是否被自动机接受。
方法
定义高阶奇偶自动机,并结合线性逻辑、指称语义与无穷重写理论来构造可判定性证明。
评估
理论证明:证明当无穷 λ-项由有限简单类型 λY-项生成时,其被高阶奇偶自动机接受的问题可判定;无实验评估。
原文摘要(Abstract)

We introduce a notion of higher-order parity automaton which extends to infinitary simply-typed λ-terms the traditional notion of parity tree automaton on infinitary ranked trees. Our main result is that the acceptance of an infinitary λ-term by a higher-order parity automaton A is decidable, whenever the infinitary λ-term is generated by a finite and simply-typed λY-term. The decidability theorem is established by combining ideas coming from linear logic, from denotational semantics and from infinitary rewriting theory.

链接与引用

DOI 原文 · DBLP

BibTeX
@inproceedings{Mellies17,
  title = {Higher-order parity automata},
  author = {Paul-André Melliès},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005077}
}