A Characterisation of First-Order Constraint Satisfaction Problems
From MaRDI portal
(Redirected from Publication:5453499)
Decidability of theories and sets of sentences (03B25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Recommendations
- Locally finite constraint satisfaction problems
- Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
- scientific article; zbMATH DE number 1670830
- Asking the Metaquestions in Constraint Tractability
- Universal Algebra and Hardness Results for Constraint Satisfaction Problems
Cited in
(41)- Universal algebra and hardness results for constraint satisfaction problems
- Affine systems of equations and counting infinitary logic
- The complexity of satisfiability problems: Refining Schaefer's theorem
- Relativised homomorphism preservation at the finite level
- Low-level dichotomy for quantified constraint satisfaction problems
- A tetrachotomy of ontology-mediated queries with a covering axiom
- Dismantlability, connectedness, and mixing in relational structures
- On digraph coloring problems and treewidth duality
- Majority constraints have bounded pathwidth duality
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- Majority functions on structures with finite duality
- Graph partitions with prescribed patterns
- Tractability in constraint satisfaction problems: a survey
- Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
- Surjective \texttt{H}-colouring over reflexive digraphs
- Constraint satisfaction, irredundant axiomatisability and continuous colouring
- List-homomorphism problems on graphs and arc consistency
- Colouring, constraint satisfaction, and complexity
- NU polymorphisms on reflexive digraphs
- Locally finite constraint satisfaction problems
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- Algebra and the complexity of digraph CSPs: a survey
- Dismantlability, Connectedness, and Mixing in Relational Structures
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
- Recent Results on the Algebraic Approach to the CSP
- Dualities for Constraint Satisfaction Problems
- Topology and Adjunction in Promise Constraint Satisfaction
- Dualities and dual pairs in Heyting algebras
- The algebraic structure of the densification and the sparsification tasks for CSPs
- Functors on relational structures which admit both left and right adjoints
- Regular families of forests, antichains and duality pairs of relational structures
- Promise and infinite-domain constraint satisfaction
- When do homomorphism counts help in query algorithms?
- The complexity of the list homomorphism problem for graphs
- The complexity of resilience problems via valued constraint satisfaction problems
- The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
- Symmetric linear arc monadic Datalog and gadget reductions
- Adaptive query algorithms for relational structures based on homomorphism counts
- The complexity of resilience problems via valued constraint satisfaction
- Absolute retracts and varieties generated by chordal graphs
This page was built for publication: A Characterisation of First-Order Constraint Satisfaction Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5453499)
