Showing cs.LOShow all
3 papers · 1 filter
cs.LO2026
When Darwin met Ianus: dichotomies of expressivity
Johanna Brunar, Michael Pinsker, Moritz Schöbi
The classifications of temporal and phylogeny constraint languages stand among the most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (…
cs.LO2026
The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
Johanna Brunar, Marcin Kozik, Tomáš Nagy +1
Two major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov's proof of the dichotomy for conservative template…
cs.LO2026
The Golden Path to Guarded Monotone Strict NP
Alexey Barsukov, Michael Pinsker, Jakub Rydval
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment and…