paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Locality and Centrality: The Variety ZG

局部性与中心性:簇 ZG
LMCS vol.Volume 19, Issue 42023匹配度 1/10 · 该论文属于纯代数自动机理论与形式语言理论,研究幺半群簇 ZG 的局部性及语言刻画,与用户关注的大模型/Agent 静态分析、浮点程序分析、贝叶斯程序分析及其与 LLM 的交叉均无直接关系。虽然涉及逻辑与自动机这一形式化方向,但未涉及程序分析工具、工程实现或 LLM。引用 0 inbox
Antoine Amarilli, Charles Paperman
crossref: 2026-09-10

AI 速览

一句话:证明群元素均中心的幺半群簇 ZG 是局部的,并将其语言刻画为单例语言与正则交换语言的不交混洗的有限并。

本文研究幺半群簇 ZG,即所有属于群的元素都与其余元素交换(中心)的幺半群类。作者关心该簇的“局部性”,探究以确定半群作半直积后是否等于局部幺半群都落在 ZG 中的半群簇 LZG。证明上借助 Straubing 延迟定理,并考察幂等元范畴中的路径。主要结果为 ZG * D = LZG,从而证明 ZG 是局部的。文中还得到代数刻画 ZG = MNil ∨ Com,并精确刻画 ZG 语言:它们恰为单例语言与正则交换语言的不交混洗的有限并。

问题
研究幺半群簇 ZG(群元素均为中心)的局部性,并刻画其对应的形式语言类。
方法
利用 Straubing 延迟定理,通过幂等元范畴中的路径分析半直积 ZG * D 与局部簇 LZG 的关系。
评估
以代数与自动机理论证明为主,给出 ZG * D = LZG、ZG = MNil ∨ Com 以及 ZG 语言的精确语言刻画,无实验评估。
原文摘要(Abstract)

We study the variety ZG of monoids where the elements that belong to a group are central, i.e., commute with all other elements. We show that ZG is local, that is, the semidirect product ZG * D of ZG by definite semigroups is equal to LZG, the variety of semigroups where all local monoids are in ZG. Our main result is thus: ZG * D = LZG. We prove this result using Straubing's delay theorem, by considering paths in the category of idempotents. In the process, we obtain the characterization ZG = MNil \vee Com, and also characterize the ZG languages, i.e., the languages whose syntactic monoid is in ZG: they are precisely the languages that are finite unions of disjoint shuffles of singleton languages and regular commutative languages.

链接与引用

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

BibTeX
@article{paperbot2190,
  title = {Locality and Centrality: The Variety ZG},
  author = {Antoine Amarilli and Charles Paperman},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 4},
  year = {2023},
  doi = {10.46298/lmcs-19(4:4)2023}
}