2026-08-21T18:34:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27482 2026-08-21T14:42:41Z ddc:004 open_access

When Darwin Met Ianus: Dichotomies of Expressivity Brunar, Johanna Pinsker, Michael Schöbi, Moritz Constraint Satisfaction Problem (CSP) Temporal Constraint language Phylogeny Constraint language pseudo-loop primitive positive interpretation polymorphism oligomorphic permutation group identity The classifications of temporal and phylogeny constraint languages stand among the most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (CSPs), yet remain the most mysterious in terms of algorithms and algebraic invariants for the tractable cases. We show that those languages which do not pp-construct EVERYTHING (and thus by the classifications 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 and phylogeny 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. Although temporal and phylogeny constraint languages appear to follow fundamentally different algorithmic principles, our proofs reveal a common core and proceed along strikingly similar lines. When Ianus can't express it all He tries in vain, he hits a wall When for 𝕂₃ no way he knows His face of pseudo-loops he shows. As Darwin finds such twisted edge To pines and vines he makes this pledge: "Should free of pseudo-loops you shine All finite structures shall be thine!" Schloss Dagstuhl – Leibniz-Zentrum für Informatik Johanna Brunar and Michael Pinsker and Moritz Schöbi 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.100 urn:nbn:de:0030-drops-274824 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.100 eng https://creativecommons.org/licenses/by/4.0/legalcode