Distributivity and residuation for lexicographic orders

Residuation theory concerns the study of partially ordered algebraic structures, most often just monoids, equipped with a weak inverse for the monoidal operator. One of its areas of application is constraint programming, whose key requirement is the presence of a distributive operator for combining...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2022-08, Vol.177, p.106271, Article 106271
Main Authors: Gadducci, Fabio, Santini, Francesco
Format: Article
Language:English
Subjects:
Formal methods
Lexicographic orders
Residuation theory
Soft constraints
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c179t-4d3e4e57dac4fb9c58820dd981bcbc58376d5d0999b3d1722865faca80b2f1f03
container_end_page
container_issue
container_start_page 106271
container_title Information processing letters
container_volume 177
creator Gadducci, Fabio
Santini, Francesco
description Residuation theory concerns the study of partially ordered algebraic structures, most often just monoids, equipped with a weak inverse for the monoidal operator. One of its areas of application is constraint programming, whose key requirement is the presence of a distributive operator for combining preferences. The key result of the paper shows how, given a residuated monoid of preferences, to build a new residuated monoid of (possibly infinite) tuples based on lexicographic order. •Residuation theory concerns the study of partially ordered algebraic structures equipped with a weak inverse.•Preference structures in several (soft) Constraint Programming (CP) frameworks adopt algebraic structures.•We extend residuation to lexicographic orders of preferences.•As far as we know, no soft CP framework allows for residuation in such orders.•This allows the use of a preference-removing operator in solving algorithms (e.g., arc consistency).
doi_str_mv 10.1016/j.ipl.2022.106271
format article
fullrecord <record><control><sourceid>elsevier_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1016_j_ipl_2022_106271</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S002001902200028X</els_id><sourcerecordid>S002001902200028X</sourcerecordid><originalsourceid>FETCH-LOGICAL-c179t-4d3e4e57dac4fb9c58820dd981bcbc58376d5d0999b3d1722865faca80b2f1f03</originalsourceid><addsrcrecordid>eNp9j8tOwzAURC0EEqHwAezyAwn3Og_HYoUKFKRKbGBtOX7AjUIT2WlF_55UYc1qNIszmsPYLUKOgPVdl9PY5xw4n3vNBZ6xBBvBsxpRnrMEgEMGKOGSXcXYAUBdFiJh4pHiFKjdT3Sg6ZjqnU2Di2T3eqJhl_ohpL37ITN8Bj1-kUmHYF2I1-zC6z66m79csY_np_f1S7Z927yuH7aZQSGnrLSFK10lrDalb6WpmoaDtbLB1rRzK0RtKwtSyrawKDhv6sproxtouUcPxYrhsmvCEGNwXo2BvnU4KgR1Mledms3VyVwt5jNzvzBuPnYgF1Q05HbGWQrOTMoO9A_9Cw3NYdk</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Distributivity and residuation for lexicographic orders</title><source>ScienceDirect Freedom Collection 2022-2024</source><source>Backfile Package - Computer Science (Legacy) [YCS]</source><source>Backfile Package - Mathematics (Legacy) [YMT]</source><creator>Gadducci, Fabio ; Santini, Francesco</creator><creatorcontrib>Gadducci, Fabio ; Santini, Francesco</creatorcontrib><description>Residuation theory concerns the study of partially ordered algebraic structures, most often just monoids, equipped with a weak inverse for the monoidal operator. One of its areas of application is constraint programming, whose key requirement is the presence of a distributive operator for combining preferences. The key result of the paper shows how, given a residuated monoid of preferences, to build a new residuated monoid of (possibly infinite) tuples based on lexicographic order. •Residuation theory concerns the study of partially ordered algebraic structures equipped with a weak inverse.•Preference structures in several (soft) Constraint Programming (CP) frameworks adopt algebraic structures.•We extend residuation to lexicographic orders of preferences.•As far as we know, no soft CP framework allows for residuation in such orders.•This allows the use of a preference-removing operator in solving algorithms (e.g., arc consistency).</description><identifier>ISSN: 0020-0190</identifier><identifier>EISSN: 1872-6119</identifier><identifier>DOI: 10.1016/j.ipl.2022.106271</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Formal methods ; Lexicographic orders ; Residuation theory ; Soft constraints</subject><ispartof>Information processing letters, 2022-08, Vol.177, p.106271, Article 106271</ispartof><rights>2022 Elsevier B.V.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c179t-4d3e4e57dac4fb9c58820dd981bcbc58376d5d0999b3d1722865faca80b2f1f03</cites><orcidid>0000-0002-3935-4696</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.sciencedirect.com/science/article/pii/S002001902200028X$$EHTML$$P50$$Gelsevier$$H</linktohtml><link.rule.ids>314,780,784,3429,3564,27924,27925,45972,46003</link.rule.ids></links><search><creatorcontrib>Gadducci, Fabio</creatorcontrib><creatorcontrib>Santini, Francesco</creatorcontrib><title>Distributivity and residuation for lexicographic orders</title><title>Information processing letters</title><description>Residuation theory concerns the study of partially ordered algebraic structures, most often just monoids, equipped with a weak inverse for the monoidal operator. One of its areas of application is constraint programming, whose key requirement is the presence of a distributive operator for combining preferences. The key result of the paper shows how, given a residuated monoid of preferences, to build a new residuated monoid of (possibly infinite) tuples based on lexicographic order. •Residuation theory concerns the study of partially ordered algebraic structures equipped with a weak inverse.•Preference structures in several (soft) Constraint Programming (CP) frameworks adopt algebraic structures.•We extend residuation to lexicographic orders of preferences.•As far as we know, no soft CP framework allows for residuation in such orders.•This allows the use of a preference-removing operator in solving algorithms (e.g., arc consistency).</description><subject>Formal methods</subject><subject>Lexicographic orders</subject><subject>Residuation theory</subject><subject>Soft constraints</subject><issn>0020-0190</issn><issn>1872-6119</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><recordid>eNp9j8tOwzAURC0EEqHwAezyAwn3Og_HYoUKFKRKbGBtOX7AjUIT2WlF_55UYc1qNIszmsPYLUKOgPVdl9PY5xw4n3vNBZ6xBBvBsxpRnrMEgEMGKOGSXcXYAUBdFiJh4pHiFKjdT3Sg6ZjqnU2Di2T3eqJhl_ohpL37ITN8Bj1-kUmHYF2I1-zC6z66m79csY_np_f1S7Z927yuH7aZQSGnrLSFK10lrDalb6WpmoaDtbLB1rRzK0RtKwtSyrawKDhv6sproxtouUcPxYrhsmvCEGNwXo2BvnU4KgR1Mledms3VyVwt5jNzvzBuPnYgF1Q05HbGWQrOTMoO9A_9Cw3NYdk</recordid><startdate>202208</startdate><enddate>202208</enddate><creator>Gadducci, Fabio</creator><creator>Santini, Francesco</creator><general>Elsevier B.V</general><scope>AAYXX</scope><scope>CITATION</scope><orcidid>https://orcid.org/0000-0002-3935-4696</orcidid></search><sort><creationdate>202208</creationdate><title>Distributivity and residuation for lexicographic orders</title><author>Gadducci, Fabio ; Santini, Francesco</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c179t-4d3e4e57dac4fb9c58820dd981bcbc58376d5d0999b3d1722865faca80b2f1f03</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Formal methods</topic><topic>Lexicographic orders</topic><topic>Residuation theory</topic><topic>Soft constraints</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Gadducci, Fabio</creatorcontrib><creatorcontrib>Santini, Francesco</creatorcontrib><collection>CrossRef</collection><jtitle>Information processing letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Gadducci, Fabio</au><au>Santini, Francesco</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Distributivity and residuation for lexicographic orders</atitle><jtitle>Information processing letters</jtitle><date>2022-08</date><risdate>2022</risdate><volume>177</volume><spage>106271</spage><pages>106271-</pages><artnum>106271</artnum><issn>0020-0190</issn><eissn>1872-6119</eissn><abstract>Residuation theory concerns the study of partially ordered algebraic structures, most often just monoids, equipped with a weak inverse for the monoidal operator. One of its areas of application is constraint programming, whose key requirement is the presence of a distributive operator for combining preferences. The key result of the paper shows how, given a residuated monoid of preferences, to build a new residuated monoid of (possibly infinite) tuples based on lexicographic order. •Residuation theory concerns the study of partially ordered algebraic structures equipped with a weak inverse.•Preference structures in several (soft) Constraint Programming (CP) frameworks adopt algebraic structures.•We extend residuation to lexicographic orders of preferences.•As far as we know, no soft CP framework allows for residuation in such orders.•This allows the use of a preference-removing operator in solving algorithms (e.g., arc consistency).</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.ipl.2022.106271</doi><orcidid>https://orcid.org/0000-0002-3935-4696</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0020-0190
ispartof Information processing letters, 2022-08, Vol.177, p.106271, Article 106271
issn 0020-0190
1872-6119
language eng
recordid cdi_crossref_primary_10_1016_j_ipl_2022_106271
source ScienceDirect Freedom Collection 2022-2024; Backfile Package - Computer Science (Legacy) [YCS]; Backfile Package - Mathematics (Legacy) [YMT]
subjects Formal methods
Lexicographic orders
Residuation theory
Soft constraints
title Distributivity and residuation for lexicographic orders
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T16%3A40%3A03IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-elsevier_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Distributivity%20and%20residuation%20for%20lexicographic%20orders&rft.jtitle=Information%20processing%20letters&rft.au=Gadducci,%20Fabio&rft.date=2022-08&rft.volume=177&rft.spage=106271&rft.pages=106271-&rft.artnum=106271&rft.issn=0020-0190&rft.eissn=1872-6119&rft_id=info:doi/10.1016/j.ipl.2022.106271&rft_dat=%3Celsevier_cross%3ES002001902200028X%3C/elsevier_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c179t-4d3e4e57dac4fb9c58820dd981bcbc58376d5d0999b3d1722865faca80b2f1f03%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true