n-almost symmetric linear arc monadic Datalog solves exactly the CSPs of structures that can be primitive positively constructed from the transitive tournament on n+2 vertices.
Two-element structures modulo primitive positive constructability
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
verdicts
UNVERDICTED 4representative citing papers
CSPs solvable by slam Datalog are exactly those admitting a gadget reduction to a Boolean CSP, equivalently characterized by unfolded caterpillar duality and the existence of quasi Maltsev and k-absorptive operations, implying decidability of expressibility.
Finite permutation groups admit a complete classification of when one arises from another by a primitive positive construction, yielding general necessary conditions for PP constructions.
Universal algebra supplies cyclic terms and bounded-width conditions that classify the tractability of finite-domain CSPs via graph homomorphisms.
citing papers explorer
-
Almost Symmetric Linear Arc Monadic Datalog and Transitive Tournaments
n-almost symmetric linear arc monadic Datalog solves exactly the CSPs of structures that can be primitive positively constructed from the transitive tournament on n+2 vertices.
-
Symmetric Linear Arc Monadic Datalog and Gadget Reductions
CSPs solvable by slam Datalog are exactly those admitting a gadget reduction to a Boolean CSP, equivalently characterized by unfolded caterpillar duality and the existence of quasi Maltsev and k-absorptive operations, implying decidability of expressibility.
-
Primitive Positive Constructions Among Finite Permutation Groups
Finite permutation groups admit a complete classification of when one arises from another by a primitive positive construction, yielding general necessary conditions for PP constructions.
-
Graph Homomorphisms and Universal Algebra
Universal algebra supplies cyclic terms and bounded-width conditions that classify the tractability of finite-domain CSPs via graph homomorphisms.