论文标题
关于时间约束满意度问题的描述性复杂性
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems
论文作者
论文摘要
有限域约束满意度问题可以通过DataLog解决，或者甚至在定点逻辑中都无法使用计数来解决。两种政权之间的边界与通用代数中重要的二分法相吻合；特别是，边界可以通过强度强的麦芽菌条件来描述。对于无限域CSP，即使CSP的模板结构在理论上是模型驯服的，情况也更为复杂。我们证明，没有MALTSEV条件来表征（Q; <）一阶还原的CSP的数据;这样的CSP称为时间CSP，在无限域约束满意度中至关重要。我们的主要结果是对时间CSP的完整分类，可以在以下逻辑形式主义之一中表达：datalog，固定点逻辑（有或不计数）或与布尔等级运算符的定点逻辑。该分类表明，有限的许多等效条件无法捕获有关时间CSP的DataLog或固定点逻辑中的表达性。
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 coincides with an important dichotomy in universal algebra; in particular, the border 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.
