an optimal solution of the abstract problem, what we can say about **optimal**
solutions of the concrete problem. Conclusions are given in the final **section.**

## 2 Semiring Constraint Satisfaction Problem

In this section we introduce several basic notions used in this paper. In particular, we give a brief summary of the theory of c-semiring based constraint satisfaction problem raised in [3] (Bistarelli, Montanari and Rossi 1997). The notion of semiring homomorphism is also introduced.

## 2.1 C-Semirings

Definition 2.1 (semirings and c-semirings [1]). **A semiring is a tuple** S = hS, +, ×, 0, 1i **such that:**
1. S **is a set and** 0, 1 ∈ S;
2. + is commutative, associative and 0 **is its unit element;**

3. × is associative, distributive over +, 1 is its unit element and 0 **is its**
absorbing element.
We call + and ×**, respectively, the** sum **and the** *product* **operation. A c-semiring**
is a semiring hS, +, ×, 0, 1i **such that:**
4. + is idempotent, 1 is its absorbing element, and × **is commutative.**
Consider the relation ≤S defined over S such that a ≤S b iff a+b = b**. Then**
it is possible to prove that [3]:
- hS, ≤Si is a lattice, 0 is its bottom and 1 **its top;**
- **+ is the** lub (lowest upper bound) operator ∨ **in the lattice** hS, ≤Si;

- × **is monotonic on** ≤S;
- If × is idempotent, that is a × a = a for each a ∈ S, then hS, ≤Si **is a**
distributive lattice and × **is its** glb **(greatest lower bound)** ∧.
Remark 2.1. **The above definition of c-semiring differs from the one given in [3]** simply in that a c-semiring, with the induced partial order, is not necessarily complete. For example, suppose Q is the set of rational number and S **= [0**, 1]∩Q
is the subalgebra of the fuzzy semiring SF CSP = h[0, 1], ∨, ∧, 0, 1i. Then S **is a** c-semiring but hS, ≤Si is not a complete lattice, where ≤S **is the partial order**
induced by the semiring S**, which happens to be the usual total order on** S.