我的阅读状态 （保存写回仓库，全设备同步；首次保存需输入访问令牌）

AI 速览

一句话：证明特定形式的二次广义多项式扩展 Presburger 算术后该理论不可判定。

本文研究 Presburger 算术在加入广义多项式后其可判定性是否保持。Presburger 算术是整数加法的一阶理论，已知可判定；作者关注由某一类特定形式的二次广义多项式对其进行的扩展。论文证明，该扩展理论是不可判定的。该结果给出了 Presburger 算术可判定性边界的一个负面结论：即使只加入二次广义多项式，而非更高次或任意函数，也可能导致理论不可判定。摘要未展开具体证明技术。

问题

加入特定形式的二次广义多项式后，Presburger 算术的扩展理论是否仍可判定。

方法

对该类扩展理论进行可判定性分析；摘要未说明具体证明技术。

评估

证明该扩展理论不可判定，从而表明这类广义多项式会破坏 Presburger 算术的可判定性。

链接与引用

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

@article{Konieczny25,
  title = {Decidability of extensions of Presburger arithmetic by generalised polynomials},
  author = {Jakub Konieczny},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 21, Issue 4},
  year = {2025},
  doi = {10.46298/lmcs-21(4:1)2025}
}