Janus-faces of temporal constraint languages: a dichotomy of expressivity
This provides new algebraic insights and uniform proofs for temporal CSPs, advancing theoretical understanding but is incremental within a specialized domain.
The paper tackles the limited expressive power of tractable temporal constraint languages in infinite-domain CSPs, showing they can only interpret limited graphs/hypergraphs and admit 4-ary pseudo-Siggers polymorphisms, which supports the Bodirsky-Pinsker conjecture.
The Bodirsky-Kára classification of temporal constraint languages stands as one of the earliest and most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (CSPs), yet it remains one of the most mysterious in terms of algorithms and algebraic invariants for the tractable cases. We show that those temporal languages which do not pp-construct EVERYTHING (and thus by the classification are solvable in polynomial time) have, in fact, very limited expressive power as measured by the graphs and hypergraphs they can pp-interpret. This limitation yields many previously unknown algebraic consequences, while also providing new, uniform proofs for known invariance properties. In particular, we show that such temporal constraint languages admit $4$-ary pseudo-Siggers polymorphisms -- a result that sustains the possibility that the existence of such polymorphisms extends to the much broader context of the Bodirsky-Pinsker conjecture.