A Characterisation of First-Order Constraint Satisfaction Problems
DOI10.2168/LMCS-3(4:6)2007zbMATH Open1131.68098OpenAlexW2165528704MaRDI QIDQ5453499FDOQ5453499
Authors: Benoît Larose, Cynthia Loten, Claude Tardif 
Publication date: 1 April 2008
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2168/lmcs-3(4:6)2007
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
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)
Cited In (34)
- List-homomorphism problems on graphs and arc consistency
- Surjective \texttt{H}-colouring over reflexive digraphs
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- Dismantlability, Connectedness, and Mixing in Relational Structures
- Graph partitions with prescribed patterns
- Dismantlability, connectedness, and mixing in relational structures
- Recent Results on the Algebraic Approach to the CSP
- Absolute retracts and varieties generated by chordal graphs
- Functors on relational structures which admit both left and right adjoints
- Tractability in constraint satisfaction problems: a survey
- Colouring, constraint satisfaction, and complexity
- Dualities for Constraint Satisfaction Problems
- The complexity of satisfiability problems: Refining Schaefer's theorem
- 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
- Majority constraints have bounded pathwidth duality
- Relativised homomorphism preservation at the finite level
- A tetrachotomy of ontology-mediated queries with a covering axiom
- Low-level dichotomy for quantified constraint satisfaction problems
- NU polymorphisms on reflexive digraphs
- Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
- The complexity of the list homomorphism problem for graphs
- 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
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Regular families of forests, antichains and duality pairs of relational structures
- Majority functions on structures with finite duality
- Locally finite constraint satisfaction problems
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)
