Soft constraint abstraction based on semiring homomorphism
| Autor: | Mingsheng Ying, Sanjiang Li |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science Computer Science - Artificial Intelligence Order-reflecting Computation Theory & Mathematics Semiring Theoretical Computer Science Combinatorics ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Constraint solving Noncommutative signal-flow graph Constraint satisfaction problem Mathematics Discrete mathematics Soft constraint satisfaction Constraint satisfaction Semiring homomorphism Abstraction (mathematics) Constraint (information theory) Artificial Intelligence (cs.AI) TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Scheme (mathematics) Homomorphism Abstraction Computer Science::Formal Languages and Automata Theory Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 403(2-3):192-201 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2008.03.029 |
| Popis: | 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)$. Comment: 18 pages, 1 figure |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect