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 universal-algebraic minor condition. For infinite-domain constraint satisfaction problems (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 (<); 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 mod-2 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.
|Number of pages||58|
|Journal||Journal of the ACM|
|Publication status||Published - Feb 2023|
DFG Classification of Subject Areas according to Review Boards
Subject groups, research areas, subject areas according to Destatis
ASJC Scopus subject areas
- Maltsev conditions, Temporal constraint satisfaction problems, fixed-point logic, Fixed-point logic