Satisfiability in semiring constraint satisfaction problems
Katarina Britz · South African Institute of Computer Scientists and Information Technologists · 2003
We present the partial satisfiability problem in a semiring constraint satisfaction problem (SCSP) framework. Interpreting the semiring of an SCSP as a lattice of truth values yields a problem in many-valued logic. As in the classical satisfiability problem statement, constraints are formulated as propositions in the logic, using the natural correspondence between semiring operations on the one hand, and connectives in the logic on the other. Partial satisfiability is defined as a binary function which assigns to each constraint in the logic a semiring value in each state, indicating the degree of satisfaction of the constraint in the given state.