A Characterisation of First-Order Constraint Satisfaction Problems
From MaRDI portal
Publication:5453499
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decidability of theories and sets of sentences (03B25) Applications of universal algebra in computer science (08A70)
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
(34)- List-homomorphism problems on graphs and arc consistency
- Locally finite constraint satisfaction problems
- Surjective \texttt{H}-colouring over reflexive digraphs
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- Graph partitions with prescribed patterns
- Dismantlability, Connectedness, and Mixing in Relational Structures
- Absolute retracts and varieties generated by chordal graphs
- Dismantlability, connectedness, and mixing in relational structures
- Tractability in constraint satisfaction problems: a survey
- Recent Results on the Algebraic Approach to the CSP
- Functors on relational structures which admit both left and right adjoints
- Colouring, constraint satisfaction, and complexity
- The complexity of satisfiability problems: Refining Schaefer's theorem
- Dualities for Constraint Satisfaction Problems
- Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- Dualities and dual pairs in Heyting algebras
- Topology and Adjunction in Promise Constraint Satisfaction
- Relativised homomorphism preservation at the finite level
- Majority constraints have bounded pathwidth duality
- A tetrachotomy of ontology-mediated queries with a covering axiom
- Low-level dichotomy for quantified constraint satisfaction problems
- NU polymorphisms on reflexive digraphs
- The complexity of the list homomorphism problem for graphs
- Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
- Constraint satisfaction, irredundant axiomatisability and continuous colouring
- Affine systems of equations and counting infinitary logic
- Universal algebra and hardness results for constraint satisfaction problems
- Algebra and the complexity of digraph CSPs: a survey
- The algebraic structure of the densification and the sparsification tasks for CSPs
- On digraph coloring problems and treewidth duality
- Regular families of forests, antichains and duality pairs of relational structures
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Majority functions on structures with finite duality
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)
