paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Equivariant ideals of polynomials

多项式的等变理想
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 1/10 · 论文属于纯代数与逻辑自动机理论,研究等变多项式理想的有限基与 Gröbner 基计算,未涉及程序静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,与研究画像的核心问题基本无关。引用 5 inbox
Arka Ghosh, Sławomir Lasota
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:研究等变多项式理想的有限基,扩展 Buchberger 算法计算 Gröbner 基并判定成员问题。

本文研究无限多变量多项式的理想。变量取自可数逻辑结构 A,A 到 A 的嵌入通过重命名变量作用于多项式。作者首先刻画 A 需满足的充分必要条件,以保证 Hilbert 基定理的如下推广成立:每个在变量重命名下不变的等变多项式理想都有限生成。其次,他们把经典 Buchberger 算法推广到该设定,用以计算给定等变理想的 Gröbner 基,由此得到等变理想成员问题的可判定性。最后概述结果在寄存器自动机、带数据 Petri 网、轨道有限生成向量空间和轨道有限线性方程组等方向的应用。

问题
研究在可数逻辑结构变量上、对变量重命名不变的等变多项式理想何时有限生成,以及其成员问题是否可判定。
方法
利用模型论、等变性与 Gröbner 基理论,给出保证有限生成的充要条件,并扩展 Buchberger 算法以计算等变理想的 Gröbner 基。
评估
通过理论证明和算法推导给出可判定性,并概述在寄存器自动机、带数据 Petri 网、轨道有限线性代数等中的应用。
原文摘要(Abstract)

We study existence and computability of finite bases for ideals of polynomials over infinitely many variables. In our setting, variables come from a countable logical structure A, and embeddings from A to A act on polynomials by renaming variables. First, we give a sufficient and necessary condition for A to guarantee the following generalisation of Hilbert's Basis Theorem: every polynomial ideal which is equivariant, i.e. invariant under renaming of variables, is finitely generated. Second, we develop an extension of classical Buchberger's algorithm to compute a Gröbner basis of a given equivariant ideal. This implies decidability of the membership problem for equivariant ideals. Finally, we sketch upon various applications of these results to register automata, Petri nets with data, orbitfinitely generated vector spaces, and orbit-finite systems of linear equations.

链接与引用

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

BibTeX
@inproceedings{0002024,
  title = {Equivariant ideals of polynomials},
  author = {Arka Ghosh and Sławomir Lasota},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662074}
}