paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Enumerating Independent Linear Inferences

枚举独立线性推理
LMCS vol.Volume 19, Issue 22023匹配度 2/10 · 论文属于逻辑与自动机/定理证明领域,研究线性推理的枚举与图形表示,与用户关注的LLM/Agent改进静态分析或形式化验证、浮点程序分析、贝叶斯程序分析均无直接关联。虽然形式化验证是用户感兴趣的AI→PL方向之一,但该论文未涉及LLM/Agent,也非程序分析或工业落地案例。引用 0 inbox
Anupam Das, Alex Rice
crossref: 2026-09-10

AI 速览

一句话:借助线性公式的图形表示高效搜索独立线性推理,发现8变量最小实例并反驳已有猜想。

线性推理是布尔代数中每个变量在两侧至多出现一次的有效不等式。此前直接基于公式的搜索在7变量时已达计算极限。本文利用近期提出的线性公式图形表示,实现更高效的 switch-medial-independent 推理搜索。结果找到四个最小8变量独立线性推理,并证明不存在更小的;其中两个可推出已有独立线性推理,另两个(互为对偶)具有此前方法难以触及的结构,且其存在性反驳了 Das 与 Straßburger 的猜想。作者还识别出10个与前述推理独立的9变量最小线性推理(5对对偶),并展示该实现对近期 graph logics 的应用。

问题
如何高效枚举线性推理并判定其独立性,突破基于公式直接搜索在7变量时遇到的计算瓶颈。
方法
利用线性公式的图形表示构建实现,搜索 switch-medial-independent 的线性推理,并证明所发现推理的最小性。
评估
枚举得到四个最小8变量独立线性推理并证明无更小者,发现10个9变量最小独立线性推理(5对对偶),并将实现应用于 graph logics。
原文摘要(Abstract)

A linear inference is a valid inequality of Boolean algebra in which each variable occurs at most once on each side. In this work we leverage recently developed graphical representations of linear formulae to build an implementation that is capable of more efficiently searching for switch-medial-independent inferences. We use it to find four `minimal' 8-variable independent inferences and also prove that no smaller ones exist; in contrast, a previous approach based directly on formulae reached computational limits already at 7 variables. Two of these new inferences derive some previously found independent linear inferences. The other two (which are dual) exhibit structure seemingly beyond the scope of previous approaches we are aware of; in particular, their existence contradicts a conjecture of Das and Strassburger. We were also able to identify 10 minimal 9-variable linear inferences independent of all the aforementioned inferences, comprising 5 dual pairs, and present applications of our implementation to recent `graph logics'.

链接与引用

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

BibTeX
@article{paperbot2216,
  title = {Enumerating Independent Linear Inferences},
  author = {Anupam Das and Alex Rice},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 2},
  year = {2023},
  doi = {10.46298/lmcs-19(2:11)2023}
}