paperbot · PL 论文追踪

全部论文 待读 收藏

P2 First-order queries on classes of structures with bounded expansion

有界扩张结构类上的一阶查询
LMCS vol.Volume 16, Issue 12020匹配度 0/10 · 该论文属于有限模型论与数据库查询求值，研究有界扩张结构上一阶查询的线性时间求值、常延迟枚举与计数，与用户关注的 PL/AI 交叉、静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析均无直接关系。引用 27 inbox
Wojtek Kazana, Luc Segoufin
逻辑与自动机
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话：重新证明有界扩张结构类上一阶查询可线性时间求值，并实现常延迟枚举与线性时间计数。

论文研究在有界扩张（bounded expansion）数据库类上评估一阶查询。有界扩张是一个较广的概念，推广了有界度、有界树宽和至少排除一个子图等结构类；此前已知一阶句子可在该结构类上线性时间求值。本文给出该结果的一个不同证明，并进一步证明一阶查询的答案可在线性时间预处理后以常数延迟枚举，且答案计数也可在线性时间内完成。

问题
研究在有界扩张结构类上如何高效评估一阶查询，包括判定满足性、枚举答案与计数答案。
方法
针对有界扩张结构类给出一种新的构造性证明与算法，分析一阶查询求值、枚举和计数的复杂度。
评估
通过理论算法与复杂度分析进行评估，证明一阶句子线性时间可求值、查询答案常延迟枚举、答案计数线性时间。
原文摘要（Abstract）

We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree, bounded treewidth and exclusion of at least one minor. It was known that over a class of databases with bounded expansion, first-order sentences could be evaluated in time linear in the size of the database. We give a different proof of this result. Moreover, we show that answers to first-order queries can be enumerated with constant delay after a linear time preprocessing. We also show that counting the number of answers to a query can be done in time linear in the size of the database.

链接与引用

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

BibTeX 
@article{abs-1802-04613,
  title = {First-order queries on classes of structures with bounded expansion},
  author = {Wojtek Kazana and Luc Segoufin},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 1},
  year = {2020},
  doi = {10.23638/lmcs-16(1:25)2020}
}