paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Wreath Products of Distributive Forest Algebras

分配森林代数的圈积
LICS Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science2018匹配度 2/10 · 该论文属于纯逻辑与自动机理论研究,讨论森林代数与 PDL 可判定性,与用户关注的静态分析、LLM/Agent 交叉、浮点程序分析、贝叶斯程序分析均无直接关联;仅与形式化验证/程序逻辑有非常间接的理论联系。引用 1 inbox
Michael Hahn, Andreas Krebs, Howard Straubing
crossref: 2026-09-12

AI 速览

一句话:证明满足二重迭代分配律的森林代数所识别语言均属于 PDL,并给出该子类的可判定性。

论文研究森林上命题动态逻辑(PDL)可定义性是否可判定这一开放问题。基于 Bojańczyk 等人用森林代数给出的代数刻画,Straubing 提出用 k 重迭代分配律逼近 PDL:若能证明所有满足该律的语言都在 PDL 中,则可判定 PDL。本文解决 k=2 的情形,证明由满足二重迭代分配律的森林代数识别的语言都属于 PDL,并进一步证明该语言类是可判定的。这给出了 PDL 的一个新的非平凡可判定子类,也表明上述基于迭代分配律的总体路线是可行的。

问题
森林上 PDL 可定义性是否可判定尚无定论;Straubing 的 k 重迭代分配律路线需要验证满足该律的语言是否都在 PDL 中。
方法
利用森林代数与圈积等代数工具,证明 k=2 时二重迭代分配律所识别的语言类包含于 PDL。
评估
通过代数证明建立包含关系,并证明该子类的可判定性;属于理论结果,无实验评估。
原文摘要(Abstract)

It is an open problem whether definability in Propositional Dynamic Logic (PDL) on forests is decidable. Based on an algebraic characterization by Bojańczyk, et. al., (2012) in terms of forest algebras, Straubing (2013) described an approach to PDL based on a k-fold iterated distributive law. A proof that all languages satisfying such a k-fold iterated distributive law are in PDL would settle decidability of PDL. We solve this problem in the case k = 2: All languages recognized by forest algebras satisfying a 2-fold iterated distributive law are in PDL. Furthermore, we show that this class is decidable. This provides a novel nontrivial decidable subclass of PDL, and demonstrates the viability of the proposed approach to deciding PDL in general.

链接与引用

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

BibTeX
@inproceedings{paperbot4330,
  title = {Wreath Products of Distributive Forest Algebras},
  author = {Michael Hahn and Andreas Krebs and Howard Straubing},
  booktitle = {LICS},
  year = {2018},
  doi = {10.1145/3209108.3209158}
}