An Algebraic Approach to Valued Constraint Satisfaction

DOI10.4230/LIPICS.CSL.2017.42zbMATH Open1440.68121OpenAlexW2756790058MaRDI QIDQ5111213FDOQ5111213

Authors: Rostislav Horčík, Tommaso Moraschini, A. Vidal 

Publication date: 26 May 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7676/pdf/LIPIcs-CSL-2017-42.pdf

Recommendations

• Algebraic properties of valued constraint satisfaction problem
• An Algebraic Characterisation of Complexity for Valued Constraint
• The complexity of valued constraint satisfaction
• The complexity of valued constraint satisfaction problems
• scientific article; zbMATH DE number 4162262
• A solution configuration and its algorithm of valuation algebras induced by a constraint semiring
• Solving set-valued constraint satisfaction problems
• Bounded backtracking for the valued constraint satisfaction problems
• Binarisation for valued constraint satisfaction problems

zbMATH Keywords

polymorphismvalued CSPpp-definabilityGeiger's theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of universal algebra in computer science (08A70)

Cited In (18)

• A definability dichotomy for finite valued CSPs
• The expressive power of valued constraints: Hierarchies and collapses
• Fuzzy intensional semantics
• The complexity of valued constraint satisfaction
• A note on some collapse results of valued constraints
• Algebraic properties of valued constraint satisfaction problem
• Fraïssé classes of graded relational structures
• Valued constraint satisfaction problems
• The complexity of valued constraint satisfaction problems
• An algebraic theory of complexity for discrete optimization.
• Binarisation for valued constraint satisfaction problems
• The complexity of general-valued CSPs
• High-order consistency in valued constraint satisfaction
• The complexity of valued CSPs
• Quantaloidal approach to constraint satisfaction
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• A Lindström theorem in many-valued modal logic over a finite MTL-chain
• The Expressive Power of Valued Constraints: Hierarchies and Collapses

This page was built for publication: An Algebraic Approach to Valued Constraint Satisfaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111213)