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