paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Solvability of orbit-finite systems of linear equations

轨道有限(orbit-finite)线性方程组的可解性
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 1/10 · 该论文属于集合论/自动机与线性代数的纯理论研究,讨论原子集合下的轨道有限线性方程组可解性,与用户关注的 LLM/Agent、静态分析、浮点程序分析、贝叶斯程序分析等方向没有直接交集。引用 6 inbox
Arka Ghosh, Piotr Hofman, Slawomir Lasota
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:在原子集合框架下给出轨道有限线性方程组可解性的判定过程,并证明其生成向量空间具有轨道有限基。

本文研究原子集合(sets with atoms)中的轨道有限线性方程组,核心问题是判定这类无限但具有对称结构的方程组是否可解。作者进一步发展了由轨道有限集生成的向量空间理论,证明每个这样的向量空间都存在轨道有限基,这一性质是构造判定过程的关键工具。所提算法在温和可有效计算假设下适用于任意域甚至交换环,将给定轨道有限系统归约为若干有限系统:一般情况下归约出的有限系统数量为指数级,但当输入系统的原子维数固定时,数量降为多项式级。该工作为轨道有限线性代数提供了可判定性结果与基础性定理。

问题
研究原子集合中轨道有限线性方程组的可解性判定问题。
方法
发展轨道有限集生成向量空间的理论,证明轨道有限基存在,并据此把轨道有限系统归约为有限系统;在温和有效性假设下适用于任意域或交换环。
评估
通过归约数量分析评估算法:一般情形指数多,固定原子维数时多项式多;同时证明轨道有限基这一基础性质。
原文摘要(Abstract)

We study orbit-finite systems of linear equations, in the setting of sets with atoms. Our principal contribution is a decision procedure for solvability of such systems. The procedure works for every field (and even commutative ring) under mild effectiveness assumptions, and reduces a given orbit-finite system to a number of finite ones: exponentially many in general, but polynomially many when the atom dimension of input systems is fixed. Towards obtaining the procedure we push further the theory of vector spaces generated by orbit-finite sets, and show that each such vector space admits an orbit-finite basis. This fundamental property is a key tool in our development, but should be also of wider interest.

链接与引用

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

BibTeX
@inproceedings{0002H022,
  title = {Solvability of orbit-finite systems of linear equations},
  author = {Arka Ghosh and Piotr Hofman and Slawomir Lasota},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533333}
}