Extending Soft Arc Consistency to Non-Invertible Semirings. Bistarelli, S., Gadducci, F., Larrosa, J., Rollon, E., & Santini, F. 2010. doi abstract bibtex We extend algorithms for arc consistency proposed in the literature in order to deal with (absorptive) semirings that are not invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings: among other instances, for those semirings obtained as the cartesian product of any family of semirings. The main application is that the new arc consistency algorithm can be used for multi-criteria soft CSPs. To reach this objective, we first show that any semiring can be transformed into a new one where the + operator is instantiated with the Least Common Divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm (when the × operator of the semiring is not idempotent). We then propose an arc consistency algorithm which takes advantage of this LCD operator.
@conference{
11391_166439,
author = {Bistarelli, Stefano and Gadducci, Fabio and Larrosa, Javier and Rollon, Emma and Santini, Francesco},
title = {Extending Soft Arc Consistency to Non-Invertible Semirings},
year = {2010},
publisher = {Springer},
volume = {6437},
booktitle = {Advances in Artificial Intelligence - 9th Mexican International Conference on Artificial Intelligence, MICAI 2010},
abstract = {We extend algorithms for arc consistency proposed in the literature in order to deal with (absorptive) semirings that are not invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings: among other instances, for those semirings obtained as the cartesian product of any family of semirings. The main application is that the new arc consistency algorithm can be used for multi-criteria soft CSPs. To reach this objective, we first show that any semiring can be transformed into a new one where the + operator is instantiated with the Least Common Divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm (when the × operator of the semiring is not idempotent). We then propose an arc consistency algorithm which takes advantage of this LCD operator.},
doi = {10.1007/978-3-642-16761-4_34},
pages = {386--398}
}
Downloads: 0
{"_id":"J6dboRkvNHDZQTviP","bibbaseid":"bistarelli-gadducci-larrosa-rollon-santini-extendingsoftarcconsistencytononinvertiblesemirings-2010","author_short":["Bistarelli, S.","Gadducci, F.","Larrosa, J.","Rollon, E.","Santini, F."],"bibdata":{"bibtype":"conference","type":"conference","author":[{"propositions":[],"lastnames":["Bistarelli"],"firstnames":["Stefano"],"suffixes":[]},{"propositions":[],"lastnames":["Gadducci"],"firstnames":["Fabio"],"suffixes":[]},{"propositions":[],"lastnames":["Larrosa"],"firstnames":["Javier"],"suffixes":[]},{"propositions":[],"lastnames":["Rollon"],"firstnames":["Emma"],"suffixes":[]},{"propositions":[],"lastnames":["Santini"],"firstnames":["Francesco"],"suffixes":[]}],"title":"Extending Soft Arc Consistency to Non-Invertible Semirings","year":"2010","publisher":"Springer","volume":"6437","booktitle":"Advances in Artificial Intelligence - 9th Mexican International Conference on Artificial Intelligence, MICAI 2010","abstract":"We extend algorithms for arc consistency proposed in the literature in order to deal with (absorptive) semirings that are not invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings: among other instances, for those semirings obtained as the cartesian product of any family of semirings. The main application is that the new arc consistency algorithm can be used for multi-criteria soft CSPs. To reach this objective, we first show that any semiring can be transformed into a new one where the + operator is instantiated with the Least Common Divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm (when the × operator of the semiring is not idempotent). We then propose an arc consistency algorithm which takes advantage of this LCD operator.","doi":"10.1007/978-3-642-16761-4_34","pages":"386–398","bibtex":"@conference{\n\t11391_166439,\n\tauthor = {Bistarelli, Stefano and Gadducci, Fabio and Larrosa, Javier and Rollon, Emma and Santini, Francesco},\n\ttitle = {Extending Soft Arc Consistency to Non-Invertible Semirings},\n\tyear = {2010},\n\tpublisher = {Springer},\n\tvolume = {6437},\n\tbooktitle = {Advances in Artificial Intelligence - 9th Mexican International Conference on Artificial Intelligence, MICAI 2010},\n\tabstract = {We extend algorithms for arc consistency proposed in the literature in order to deal with (absorptive) semirings that are not invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings: among other instances, for those semirings obtained as the cartesian product of any family of semirings. The main application is that the new arc consistency algorithm can be used for multi-criteria soft CSPs. To reach this objective, we first show that any semiring can be transformed into a new one where the + operator is instantiated with the Least Common Divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm (when the × operator of the semiring is not idempotent). We then propose an arc consistency algorithm which takes advantage of this LCD operator.},\n\tdoi = {10.1007/978-3-642-16761-4_34},\t\n\tpages = {386--398}\n}\n","author_short":["Bistarelli, S.","Gadducci, F.","Larrosa, J.","Rollon, E.","Santini, F."],"key":"11391_166439","id":"11391_166439","bibbaseid":"bistarelli-gadducci-larrosa-rollon-santini-extendingsoftarcconsistencytononinvertiblesemirings-2010","role":"author","urls":{},"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"conference","biburl":"http://www.dmi.unipg.it/~bista/papers/pubblicazioni.bib","dataSources":["GhB5rb8JzW6az3exo"],"keywords":[],"search_terms":["extending","soft","arc","consistency","non","invertible","semirings","bistarelli","gadducci","larrosa","rollon","santini"],"title":"Extending Soft Arc Consistency to Non-Invertible Semirings","year":2010}