paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Simple Classes of Automatic Structures

自动结构的简单类
LMCS vol.Volume 22, Issue 12026匹配度 1/10 · 该论文属于自动机与逻辑的基础理论研究，关注多项式增长自动结构和 Presburger 结构的代数刻画，与静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析没有直接关联。引用 0 inbox
Achim Blumensath
逻辑与自动机
crossref: 2026-09-10

AI 速览

一句话：研究多项式增长自动结构与Presburger结构两类子类，刻画其中群和等价结构的代数性质。

本文关注自动结构类的两个较简单子类：多项式增长的自动结构，以及Presburger结构。自动结构是可用有限自动机表示其域、关系和运算的结构，在模型论与自动机理论中具有可判定性等良好性质。作者针对这两类子类中的群和等价结构，给出代数刻画，即用代数条件或不变量精确描述这些结构何时属于相应子类。论文属于理论工作，结果以数学定理形式呈现，为理解自动结构的分类与代数性质提供基础。

问题
如何刻画自动结构的两个子类——多项式增长自动结构与Presburger结构——中的群和等价结构？
方法
采用代数与自动机/模型论方法，建立这两类子类中群和等价结构的代数特征。
评估
以数学定理形式给出并证明相关代数刻画，属于理论结果，不涉及实验评估。
原文摘要（Abstract）

We study two subclasses of the class of automatic structures: automatic structures of polynomial growth and Presburger structures. We present algebraic characterisations of the groups and the equivalence structures in these two classes.

链接与引用

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

BibTeX 
@article{abs-2505-22821,
  title = {Simple Classes of Automatic Structures},
  author = {Achim Blumensath},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 22, Issue 1},
  year = {2026},
  doi = {10.46298/lmcs-22(1:5)2026}
}