Copyright Information
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of
scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other
copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying
this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without
the explicit permission of the copyright holder.
Sensoria Bibliography Site Enhancing constraints manipulation in semiring-based formalisms
Stefano Bistarelli, Fabio Gadducci
abstract:
Many semiring-like structures are used in Soft Constraint Satisfaction Problems (SCSPs). We review a few properties of semirings that are useful for dealing with soft constraints, highlighting the differences between alternative proposals in the literature. We then extend the semiring structure, by adding the notion of division as weak kind of inverse operation of product. In particular, division is needed to apply constraint relaxation when the product operation of the semiring is not idempotent. The division operator is introduced via residuation and is also able to deal with partial orders, generalizing the approach given for valued CSPs.