Semiring–based and valued CSPs revisited
摘要
An a posteriori revisit of the accumulated results on the Semiring and Valued constraint satisfaction problems and related problems, showing how semi-rings and monoids (or semi-groups) are useful objects to explore the intricate interplay between expressivity and the design of efficient, correct and convergent algorithms in computer science, showing tight relationships and scientific overlaps with probabilistic reasoning over graphical structures and linear or polynomial discrete mathematical programming.