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