On the Descriptive Complexity of Temporal Constraint Satisfaction Problems.

Research output: Contribution to journalResearch articleContributedpeer-review



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.


Original languageEnglish
Article number3566051
Pages (from-to)1-58
Number of pages58
JournalJournal of the ACM
Issue number1
Publication statusPublished - Feb 2023

External IDs

Scopus 85147249842
WOS 000912554900002
ORCID /0000-0001-8228-3611/work/142241227


DFG Classification of Subject Areas according to Review Boards

Subject groups, research areas, subject areas according to Destatis


  • Maltsev conditions, Temporal constraint satisfaction problems, fixed-point logic, Fixed-point logic