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 a weak 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 it is also able to deal with partial orders, generalizing the approach given for Valued CSPs.

Enhancing constraints manipulation in semiring-based formalisms

GADDUCCI, FABIO
2006-01-01

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 a weak 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 it is also able to deal with partial orders, generalizing the approach given for Valued CSPs.
2006
1586036424
File in questo prodotto:
File Dimensione Formato  
ecai2006.pdf

solo utenti autorizzati

Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 187.25 kB
Formato Adobe PDF
187.25 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/102467
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 59
  • ???jsp.display-item.citation.isi??? 46
social impact