Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Automorphisms and endomorphisms of algebraic structures (08A35) Logic in computer science (03B70) Equational classes, universal algebra in model theory (03C05) Descriptive complexity and finite models (68Q19)

Cites Work

Existence theorems for weakly symmetric operations
Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
The reducts of equality up to primitive positive interdefinability
Non-dichotomies in Constraint Satisfaction Complexity
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
Reasoning about temporal relations
Cores of Countably Categorical Structures
Fixed-point definability and polynomial time on graphs with excluded minors
Conjunctive-query containment and constraint satisfaction
Characterizations of several Maltsev conditions.
Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
The collapse of the bounded width hierarchy
Constraint Satisfaction Problems Solvable by Local Consistency Methods
Title not available (Why is that?)
Decidability of definability
Dualities for Constraint Satisfaction Problems
The complexity of equality constraint languages
Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
Bounded width problems and algebras
Computer Science Logic
On the Power of k-Consistency
A Subalgebra Intersection Property for Congruence Distributive Varieties
Discrete temporal constraint satisfaction problems
Equivalence constraint satisfaction problems
The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
Graph isomorphism in quasipolynomial time (extended abstract)
All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
PROJECTIVE CLONE HOMOMORPHISMS
Datalog and constraint satisfaction with infinite templates
Complexity of infinite-domain constraint satisfaction
Temporal constraint satisfaction problems in fixed-point logic
Asking the Metaquestions in Constraint Tractability
The wonderland of reflections
The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
The pebbling comonad in finite model theory
Weak consistency notions for all the CSPs of bounded width
A proof of the CSP dichotomy conjecture
A dichotomy for first-order reducts of unary structures
Constraint satisfaction problems for reducts of homogeneous graphs
Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
Pseudo‐loop conditions
A complexity dichotomy for poset constraint satisfaction
Title not available (Why is that?)
Title not available (Why is that?)
A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
\( \omega \)-categorical structures avoiding height 1 identities
On the relational width of first-order expansions of finitely bounded homogeneous binary cores with bounded strict width
Title not available (Why is that?)

This page was built for publication: Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6654559)