An Algebraic Approach to Valued Constraint Satisfaction

DOI10.4230/LIPICS.CSL.2017.42MaRDI QIDQ5111213zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(19)

• The expressive power of valued constraints: Hierarchies and collapses
• A definability dichotomy for finite valued CSPs
• 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
• High-order consistency in valued constraint satisfaction
• An algebraic theory of complexity for discrete optimization.
• Binarisation for valued constraint satisfaction problems
• The complexity of general-valued CSPs
• The complexity of valued CSPs
• Quantaloidal approach to constraint satisfaction
• Homomorphism preservation theorems for many-valued structures
• 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)