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