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

(18)

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

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)