paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The logic of counting query answers

计数查询答案的逻辑
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 2/10 · 该论文研究一阶逻辑查询答案计数的可处理性与逻辑扩展,属于描述复杂性和逻辑/自动机理论,与用户关注的静态分析、Agentic/LLM、浮点程序分析及贝叶斯程序分析没有直接关联。仅在“逻辑用于程序分析基础”这一非常宽泛的意义上有间接联系,因此匹配度较低。引用 8 inbox
Hubie Chen, Stefan Mengel
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:提出并研究一种扩展一阶逻辑,用其自然表达有限结构上一阶公式答案计数的算法,以刻画易解情形。

本文研究在有限结构上计数一阶公式答案数量的问题。作者提出并研究一阶逻辑的一种扩展,使得针对该计数问题的算法可以在该逻辑中自然且方便地表达;文中将这种“自然表达”的含义精确化,并受理解计数问题易解情形的动机驱动。工作属于有限模型论与描述复杂性方向,目标是通过逻辑扩展来刻画计数查询答案的可处理情形。摘要未报告具体实验评估,主要贡献是形式化框架与理论分析。

问题
研究在有限结构上计数一阶公式答案数量的问题,并希望理解该计数问题的易解情形。
方法
提出并研究一阶逻辑的一种扩展,使计数算法能在该逻辑中自然表达,并精确界定这种表达方式的含义。
评估
摘要未描述实验评估;工作以形式化定义和理论分析为主,围绕逻辑扩展与计数可处理性的关系展开。
原文摘要(Abstract)

We consider the problem of counting the number of answers to a first-order formula on a finite structure. We present and study an extension of first-order logic in which algorithms for this counting problem can be naturally and conveniently expressed, in senses that are made precise and that are motivated by the wish to understand tractable cases of the counting problem.

链接与引用

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

BibTeX
@inproceedings{ChenM17,
  title = {The logic of counting query answers},
  author = {Hubie Chen and Stefan Mengel},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005085}
}