paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The Power-Set Construction for Tree Algebras

树代数的幂集构造
LMCS vol.Volume 19, Issue 42023匹配度 1/10 · 该论文属于范畴论/形式语义，研究树代数与上闭幂集单子之间的分配律，与用户关注的静态分析、LLM/Agent、浮点程序分析和贝叶斯程序分析均无直接交集。虽然涉及理论形式化，但缺乏工程实现、工业落地或与 AI/LLM 的交叉。引用 0 inbox
Achim Blumensath
形式语义
crossref: 2026-09-10

AI 速览

一句话：证明线性树单子与上闭幂集单子之间存在分配律，并证非线性情形不存在。

论文研究树类与树代数上的幂集操作，目标是在树单子与幂集单子之间建立分配律，从而把幂集构造与树构造良好组合。作者重点考虑上闭幂集单子，并在所有树均为线性的条件下给出主要结果：存在树单子到上闭幂集单子的分配律。对于非线性树，论文进一步证明这样的分配律不存在，从而划定了幂集构造与树结构相容的边界。该结果属于代数/范畴语义中的单子组合研究，为树代数上的非确定性/幂集式语义提供基础。

问题
如何定义树单子与幂集单子之间的分配律，以组合树构造与幂集/非确定性语义；线性树与非线性树是否存在差异。
方法
采用单子与分配律的范畴/代数方法，研究树类与树代数上的上闭幂集操作。
评估
以数学证明给出线性树情形下的存在性结果，以及非线性树情形下的不可能性结果。
原文摘要（Abstract）

We study power-set operations on classes of trees and tree algebras. Our main result consists of a distributive law between the tree monad and the upwards-closed power-set monad, in the case where all trees are assumed to be linear. For non-linear ones, we prove that such a distributive law does not exist.

链接与引用

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

BibTeX 
@article{paperbot2186,
  title = {The Power-Set Construction for Tree Algebras},
  author = {Achim Blumensath},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 4},
  year = {2023},
  doi = {10.46298/lmcs-19(4:9)2023}
}