paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Temporal Constraint Satisfaction Problems in Fixed-Point Logic

不动点逻辑中的时态约束满足问题
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 2/10 · 该论文属于逻辑与约束满足的理论研究,虽涉及 Datalog 与不动点逻辑,但与用户核心方向(静态分析×ML/Agent、浮点程序分析、贝叶斯程序分析及其与 LLM 的交叉)几乎没有直接关联;既无程序分析应用,也无 LLM/Agent 或工业落地内容。引用 1 inbox
Manuel Bodirsky, Wied Pakusa, Jakub Rydval
crossref: 2026-09-12

AI 速览

一句话:证明时态 CSP 在 Datalog 与(计数/秩)不动点逻辑中的可表达性,并给出完整分类,表明有限域 Maltsev 条件无法推广。

有限域约束满足问题(CSP)要么可由 Datalog 求解,要么甚至不能用计数不动点逻辑(FP+C)表达,其分界可由强 height-one Maltsev 条件刻画。对于无限域 CSP,即使模板在模型论上温和,情形也更复杂。本文研究 (Q;<) 的一阶归约所定义的时态 CSP,证明不存在一个 Maltsev 条件能刻画这类 CSP 的 Datalog 可表达性。主要结果给出了时态 CSP 在 Datalog、不动点逻辑(含或不含计数)以及带 Boolean rank 算子的不动点逻辑中的可表达性的完整分类。该分类表明,有限域情形中的许多等价条件在时态 CSP 上已不再等价。

问题
研究无限域时态 CSP((Q;<) 的一阶归约)在 Datalog 与各类不动点逻辑中的可表达性,以及是否存在类似有限域的 Maltsev 条件来刻画 Datalog 可表达性。
方法
通过模型论与逻辑表达性分析,对时态 CSP 在 Datalog、(计数)不动点逻辑和带 Boolean rank 算子的不动点逻辑中进行分类,并证明不存在刻画 Datalog 的 Maltsev 条件。
评估
属于理论证明与分类工作,不涉及实验评估;结果以形式化定理给出,并比较有限域与无限域时态 CSP 中若干等价条件的失效情况。
原文摘要(Abstract)

Finite-domain constraint satisfaction problems are either solvable by Datalog, or not even expressible in fixed-point logic with counting. The border between the two regimes can be described by a strong height-one Maltsev condition. For infinite-domain CSPs, the situation is more complicated even if the template structure of the CSP is model-theoretically tame. We prove that there is no Maltsev condition that characterizes Datalog already for the CSPs of first-order reducts of (Q; <); such CSPs are called temporal CSPs and are of fundamental importance in infinite-domain constraint satisfaction. Our main result is a complete classification of temporal CSPs that can be expressed in one of the following logical formalisms: Datalog, fixed-point logic (with or without counting), or fixed-point logic with the Boolean rank operator. The classification shows that many of the equivalent conditions in the finite fail to capture expressibility in Datalog or fixed-point logic already for temporal CSPs.

链接与引用

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

BibTeX
@inproceedings{paperbot5505,
  title = {Temporal Constraint Satisfaction Problems in Fixed-Point Logic},
  author = {Manuel Bodirsky and Wied Pakusa and Jakub Rydval},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394750}
}