paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs

在弦无爪图上捕获对数空间与多项式时间
LMCS vol.Volume 15, Issue 32019匹配度 1/10 · 该论文属于描述复杂性/有限模型论与图算法理论，研究弦无爪图上的 LREC= 可定义正则化及其对数空间/多项式时间捕获，与用户关注的程序分析、LLM/Agent、浮点程序分析、贝叶斯程序分析均无直接关联。引用 3 inbox
Berit Grußien
逻辑与自动机
crossref: 2026-09-10

AI 速览

一句话：证明弦无爪图类具有LREC_=可定义的正则化，由此得到对数空间同构测试并捕获对数空间与多项式时间。

本文研究描述复杂性中逻辑能否在特定图类上捕获复杂度类。作者证明弦无爪图类允许 LREC_= 可定义的正则化；LREC_= 是在一阶逻辑上加入计数与受限递归算子、可在对数空间求值的逻辑。由此得到弦无爪图的 logspace 正则化算法与同构测试，并且 LREC_= 在该图类上捕获对数空间。又因 LREC_= 包含于带计数的固定点逻辑 FPC，所以 FPC 在该图类上捕获多项式时间。结果连接图类正则化、逻辑表达能力与复杂度类。

问题
描述复杂性中，LREC_= 和带计数的固定点逻辑(FPC)能否在特定受限图类上捕获对数空间与多项式时间，以及弦无爪图是否具有对数空间正则化与同构测试。
方法
通过构造弦无爪图类的 LREC_= 可定义正则化，利用 LREC_= 的计数与受限递归表达能力，并结合 LREC_= 包含于 FPC 这一事实进行推导。
评估
理论证明：给出 logspace 正则化算法与同构测试，并推出 LREC_= 在弦无爪图上捕获对数空间、FPC 在其上捕获多项式时间。
原文摘要（Abstract）

We show that the class of chordal claw-free graphs admits LREC$_=$-definable canonization. LREC$_=$ is a logic that extends first-order logic with counting by an operator that allows it to formalize a limited form of recursion. This operator can be evaluated in logarithmic space. It follows that there exists a logarithmic-space canonization algorithm, and therefore a logarithmic-space isomorphism test, for the class of chordal claw-free graphs. As a further consequence, LREC$_=$ captures logarithmic space on this graph class. Since LREC$_=$ is contained in fixed-point logic with counting, we also obtain that fixed-point logic with counting captures polynomial time on the class of chordal claw-free graphs.Comment: 34 pages, 13 figures

链接与引用

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

BibTeX 
@article{paperbot783,
  title = {Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs},
  author = {Berit Grußien},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 3},
  year = {2019},
  doi = {10.23638/lmcs-15(3:2)2019}
}