Dualities for Constraint Satisfaction Problems
From MaRDI portal
(Redirected from Publication:5504701)
Recommendations
Cites work
- A Characterisation of First-Order Constraint Satisfaction Problems
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- A Subalgebra Intersection Property for Congruence Distributive Varieties
- Affine Systems of Equations and Counting Infinitary Logic
- Bi‐arc graphs and the complexity of list homomorphisms
- Bounded width problems and algebras
- CD(4) has bounded width
- Characterising tractable constraints
- Classification of homomorphisms to oriented cycles and of k-partite satisfiability
- Classifying the Complexity of Constraints Using Finite Algebras
- Combinatorial problems raised from 2-semilattices
- Complexity classifications of Boolean constraint satisfaction problems
- Conjunctive-query containment and constraint satisfaction
- Constraint Satisfaction Problems with Infinite Templates
- Constraints, consistency and closure
- Datalog and constraint satisfaction with infinite templates
- Datalog and Constraint Satisfaction with Infinite Templates
- Duality and Polynomial Testing of Tree Homomorphisms
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Existence theorems for weakly symmetric operations
- From graph coloring to constraint satisfaction: there and back again
- Handbook of constraint programming.
- Homomorphisms to oriented paths
- scientific article; zbMATH DE number 3972929 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1487982 (Why is no real title available?)
- scientific article; zbMATH DE number 878894 (Why is no real title available?)
- Linear Datalog and Bounded Path Duality of Relational Structures
- Majority constraints have bounded pathwidth duality
- Majority functions on structures with finite duality
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- On classes of relations and graphs determined by subobjects and factorobjects
- On digraph coloring problems and treewidth duality
- On homomorphisms to acyclic local tournaments
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- On the expressive power of Datalog: tools and a case study.
- On tractability and congruence distributivity
- Parity, circuits, and the polynomial-time hierarchy
- Posets, near unanimity functions and zigzags
- Recent Results on the Algebraic Approach to the CSP
- Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
- Some new good characterizations for directed graphs
- Tame congruence theory
- The complexity of constraint satisfaction: an algebraic approach
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Existence of Homomorphisms to Oriented Cycles
- The structure of finite algebras
- There are no pure relational width 2 constraint satisfaction problems
- Tractability and learnability arising from algebras with few subpowers
- Universal Algebra and Hardness Results for Constraint Satisfaction Problems
Cited in
(45)- Dualities in full homomorphisms
- A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
- Dismantlability, connectedness, and mixing in relational structures
- On Maltsev digraphs
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- Graph partitions with prescribed patterns
- Tractability in constraint satisfaction problems: a survey
- Robustly solvable constraint satisfaction problems
- On algebras with many symmetric operations
- Near unanimity constraints have bounded pathwidth duality
- On Maltsev digraphs
- On the CSP Dichotomy Conjecture
- scientific article; zbMATH DE number 4133855 (Why is no real title available?)
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- Tree dualities for constraint satisfaction
- scientific article; zbMATH DE number 5531977 (Why is no real title available?)
- List-homomorphism problems on graphs and arc consistency
- scientific article; zbMATH DE number 2084742 (Why is no real title available?)
- Colouring, constraint satisfaction, and complexity
- NU polymorphisms on reflexive digraphs
- \(n\)-permutability and linear Datalog implies symmetric Datalog
- Boolean topological graphs of semigroups: the lack of first-order axiomatization
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Algebra and the complexity of digraph CSPs: a survey
- Solving CSPs using weak local consistency
- Dismantlability, Connectedness, and Mixing in Relational Structures
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Finite dualities, in particular in full homomorphisms
- Quasi-equational bases for graphs of semigroups, monoids and groups.
- Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
- Recent Results on the Algebraic Approach to the CSP
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- PTAS for Sparse General-valued CSPs
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- Constraint satisfaction, graph isomorphism, and the pebbling comonad
- Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
- Regular families of forests, antichains and duality pairs of relational structures
- Right-adjoints for Datalog programs
- The complexity of the list homomorphism problem for graphs
- Local consistency as a reduction between constraint satisfaction problems
- Symmetric linear arc monadic Datalog and gadget reductions
- Generalized completion problems with forbidden tournaments
- There are no pure relational width 2 constraint satisfaction problems
- CSP duality and trees of bounded pathwidth
This page was built for publication: Dualities for Constraint Satisfaction Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5504701)
