Computer Science – Artificial Intelligence
Scientific paper
2007-05-05
Theoretical Computer Science 403(2-3) 192-201, 2008
Computer Science
Artificial Intelligence
18 pages, 1 figure
Scientific paper
10.1016/j.tcs.2008.03.029
The semiring-based constraint satisfaction problems (semiring CSPs), proposed by Bistarelli, Montanari and Rossi \cite{BMR97}, is a very general framework of soft constraints. In this paper we propose an abstraction scheme for soft constraints that uses semiring homomorphism. To find optimal solutions of the concrete problem, the idea is, first working in the abstract problem and finding its optimal solutions, then using them to solve the concrete problem. In particular, we show that a mapping preserves optimal solutions if and only if it is an order-reflecting semiring homomorphism. Moreover, for a semiring homomorphism $\alpha$ and a problem $P$ over $S$, if $t$ is optimal in $\alpha(P)$, then there is an optimal solution $\bar{t}$ of $P$ such that $\bar{t}$ has the same value as $t$ in $\alpha(P)$.
Li Sanjiang
Ying Mingsheng
No associations
LandOfFree
Soft constraint abstraction based on semiring homomorphism does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Soft constraint abstraction based on semiring homomorphism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Soft constraint abstraction based on semiring homomorphism will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-28711