paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Languages with Decidable Learning: A Meta-theorem

具有可判定学习的语言:一个元定理
OOPSLA 7(OOPSLA1)2023匹配度 3/10 · 论文属于程序合成、逻辑与自动机以及可判定学习的理论工作,与用户核心关注的 LLM/Agent 结合静态分析、浮点程序分析、贝叶斯程序分析等方向没有直接交集;虽然涉及程序合成和形式化方法,但未讨论 LLM/Agent、工业落地或相关 benchmark。引用 4 inbox
Paul Krogmeier, P. Madhusudan
crossref: 2026-09-10

AI 速览

一句话:提出 finite-aspect checkable 语言,并用树自动机元定理统一证明多类表达式学习问题可判定。

本文研究带语法限制的表达式学习问题,旨在刻画哪些符号语言的学习是可判定的。作者提出 finite-aspect checkable 语言类:其语义可由与表达式规模无关、但依赖固定求值结构的有界辅助信息定义。为统一处理此类语言,论文设计了一种用于编写表达式语法树求值程序的通用编程语言,并证明元定理:若某语言可由该语言中的程序定义,则它可对应到有限树自动机。由此,研究者只需编写程序,即可为多个表达式学习问题导出新的可判定性结果与判定过程。

问题
对带语法限制的表达式学习问题,如何判定其可学习性并统一构造判定过程。
方法
引入 finite-aspect checkable 语言,以固定结构上的有界辅助信息定义语义,并设计通用编程语言描述语法树求值;证明其与有限树自动机对应。
评估
通过在该语言中编写程序,为多个表达式学习问题导出新的可判定性结果与判定过程,体现元定理的通用性。
原文摘要(Abstract)

We study expression learning problems with syntactic restrictions and introduce the class of finite-aspect checkable languages to characterize symbolic languages that admit decidable learning. The semantics of such languages can be defined using a bounded amount of auxiliary information that is independent of expression size but depends on a fixed structure over which evaluation occurs. We introduce a generic programming language for writing programs that evaluate expression syntax trees, and we give a meta-theorem that connects such programs for finite-aspect checkable languages to finite tree automata, which allows us to derive new decidable learning results and decision procedures for several expression learning problems by writing programs in the programming language.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot2017,
  title = {Languages with Decidable Learning: A Meta-theorem},
  author = {Paul Krogmeier and P. Madhusudan},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {7},
  number = {OOPSLA1},
  year = {2023},
  doi = {10.1145/3586032}
}